Notations: les majuscules sont utilisées pour les non-terminaux, S est le symbole initial.
On considère deux grammaires: G1=(
S1-> aQ, Q->S1b,S1->e) et
G2= ( S2->AB|BC, A->BA|a,B->CC|b, C->AB|a).
Soient L1=L(G1) et L2=L(G2) leurs langages.
Trouver si possible les grammaires pour L1·L2, L1*, L1UL2, L1nL2. Est-ce que baaba est dans L1? dans L2?
On considère l'automate à pile suivant (il démarre avec le symbole Z dans la pile). Est-ce qu'il accepte les mots: aba, aabb, aaabb? Quel est son langage ?
Construire les automates à pile pour les langages suivants: