Eléments d’ informatique théorique

Série 6

Lemme du Pompage et Automates à pile

Exercice 6.1 Dites si les langages suivants sont réguliers ou non. Si vous pensez que non, utilisez le lemme du pompage, si vous pensez oui, exhibez un modèle de votre convenance qui engendre, génère ou accepte le langage.

1. Le langage engendré par l’expression régulière r = 1(0 + 1)^{∗}.

2. Le langage sur {0, 1} définit par L = {0^{n}x | x ∈ r et |x| ⩾ n}.

3. Le langage engendré par la grammaire ⟨{a, 1}, {S, Z}, {S → aSZ | ϵ, Z → 1}, S⟩.

4. Le langage sur {a, b, c} définit par L = {a^{n}b^{m}c^{p} | n + m = p}.

5. Le langage sur Σ définit par L = Σ^{∗} ∖ L où L est un langage fini.

6. Le langage définit par L = {ω ∈ {0, 1}^{∗} | ω est un palindrome}.

7. Le langage L définit sur {a, b} tel que pour tout ω ∈ L, ω vérifie

• la valeur absolue de la différence entre le nombre de a et le nombre de b de ω est strictement inférieure à 4.

• tout préfixe de ω est dans L, c’est-à-dire, ∀ ω_{1}ω_{2} ∈ L alors ω_{1} ∈ L. Exercice 6.2 Le langage résultant de l’union d’un langage fini et d’un langage non-régulier est-il régulier? Si vous pensez que oui, donnez une démonstration, si vous pensez que non trouver un contre-exemple ou une démonstration. Que dire de l’intersection? Exercice 6.3 Construire les automates à pile acceptant les languages

1. {a^{n}b^{2n} | n ≥ 0}.

2. L = {a^{n}b^{m}a^{m}b^{n} | n, m ≥ 1},

3. L^{∗}.

4. {ww^{r} | w ∈ {a, b}^{∗}}.

5. {a^{n}b^{m}a^{m}b^{n} | n, m ≥ 1}.

6. les expressions régulières sur l’aphabet {a, b}.

Exercice 6.4 Appliquer le lemme de pompage pour prouver que le langage des expressions régulières sur {a, b} n’est pas régulier.

Exercice 6.5 La grammaire suivante est-elle ambiguë (I représente une instruction d’un langage de programmation et E une expression booléène) ?

I → si E alors I | si E alors I sinon I | s_{1} | s_{2} | … | s_{n}
E → e_{1} | e_{2} | … | e_{n}