Linguaggi Regolari
Dati due linguaggi regolari $A$ e $B$ è possibile decidere se:
1)$A = B$
2)$A sube B$
Ho provato a risolverli così:
$A = B$ se e solo se esiste un automa a stati finiti che riconosce sia $A$ che $B$. (E' corretto?)
Però non riesco a svolgere il punto due,mi potete dare qualche dritta?
1)$A = B$
2)$A sube B$
Ho provato a risolverli così:
$A = B$ se e solo se esiste un automa a stati finiti che riconosce sia $A$ che $B$. (E' corretto?)
Però non riesco a svolgere il punto due,mi potete dare qualche dritta?
Risposte
Ciao! ho iniziato da poco a studiare teoria degli automi e dei linguaggi regolari e la tua domanda mi ha incuriosito.
1) Sbagli nella scelta del quantificatore. Esiste un automa a stati finiti che riconosce $A$ e $B$ anche se $A != B$ ed è il FSA che riconosce $A + B$.
2) Una volta trovata la soluzione al punto 1 il ragionamento per questa parte deve essere analogo.
1) Sbagli nella scelta del quantificatore. Esiste un automa a stati finiti che riconosce $A$ e $B$ anche se $A != B$ ed è il FSA che riconosce $A + B$.
2) Una volta trovata la soluzione al punto 1 il ragionamento per questa parte deve essere analogo.