TD11 - Automates et Langages - RICM

Notations:  les majuscules sont utilisées pour les non-terminaux, S est le symbole initial.

Exercice 1. Votre  premier automate à pile

On considère l'automate à pile suivant (il demarre avec le symbole Z dans la pile). Est-ce qu'il accepte les mots: aba,  aabb, aaabb? Quel est son langage ?

Exercice 2. On construit des automates à pile

Construire les automates à pile pour les langages suivants:

1. Palindromes sur l'alphabet {a,b}
2. {a^m bⁿ aⁿb^m| m,n Î N}
3. {a^m bⁿ c^m+n| m,n Î N}
4. Tous les mots sur {a,b} qui ont autant de a que de b
5. Toutes les séquences de parenthèses bien balancées : telles que (()(()))()
6. Les expressions arithmétiques sur les variables x,y : telles que (x+y).x 

Exercice 3. On manipule les langages hors contexte

On considère deux grammaires: G1=( S₁-> aQ, Q->S₁b,S₁->ε) et G2= ( S₂->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, L1∩L2. Est-ce que baaba est dans L1? dans L2?