Sia A un automa finito a k stati per il linguaggio L. Sia w=u.v.z una parola
di L e |v|>=k. Si dimostri che esistono v1,v2,v3, tali che:
v=v1.v2.v3 ed inoltre per ogni i naturale, u.v1.v2^i.v3.z appartiene
ad L (notazione: v^i, potenza i di v)..
Si dica quali dei seguenti linguaggi e' regolare e per esso si dia una
grammatica regolare:
tutte e sole le parole formabili sull'alfabeto Sigma = {a,b,c} tali che
"a" occorra piu' volte di "c".
tutte e sole le parole formabili sull'alfabeto Sigma = {a,b,c} tali che
"a" occorra meno volte di "c".
tutte e sole le parole formabili sull'alfabeto Sigma = {a,b,c} tali che
"a" occorra solo se preceduto (anche non immediatamente) da almeno un'occorrenza
di "c".
tutte e sole le parole formabili sull'alfabeto Sigma = {a,b,c} tali che
"a" occorra un ugual numero di volte di "c".
tutte e sole le parole formabili sull'alfabeto Sigma = {a,b,c} tali che
"a" occorra solo se "c" (anche non immediatamente) occorrenza.