TD11 - Automates et Langages - RICM

Exercice 1. Encore un langage non-régulier

Prouver que le langage E={w| |w|=2ⁿ} sur {a,b} n'est pas régulier.

supposer le contraire
prendre un mot w concret assez long dans E - c'est vous qui choisissez
imaginer sa decomposition gonflable (elle existe par "pumping lemma", mais ce n'est pas vous qui choisissez)
montrer que la version gonflée de ce mot est dans E (par "pumping lemma")
montrer que cette même version gonflée n'est pas de longueur 2ⁿ
déduire la contradiction et términer la preuve

Une autre méthode pour ceux qui comprennent parfaitement la méthode précédente. Par théorème de Myhill-Nerode il suffit de trouver l'infinité de dérivées différentes.

Calculer les dérivées a^k\E
Montrer qu'elles sont toutes différentes
En déduire la non-régularité

Exercice 2. Trois définitions inductives à analyser

1. On considère la définition de liste suivante

Base : a, b, c, ()
Règle (binaire): u,(v) -> (u v)

Montrez que ((ab)((ac)())d) est une liste. Trouvez sa dérivation. Dessinez l'arbre syntaxique. Est-il unique (est la définition non-ambigue)?

2. On considère la théorie suivante

Axiome : =+
Règles d'inférence: w->|w| et u=v ->|u = |v

Montrez que ||||=||+|| est un théorème. Trouvez sa preuve. Dessinez l'arbre de preuve. Est-il unique (est la définition non-ambigue)?

3. On considère un sous-ensemble E d'entiers défini par

Base : 0
Règles (unaires): x -> x+6 x-> x+15 x >5 -> x-6 x>14 ->x-15

Expliquez l'écriture. Montrez que 9 est dans E. Décriver E explicitement. Est la définition ambigue?

Exercice 3. Quatre définitions inductives à concevoir

Définir par des schémas d'induction

les écritures de naturels en système décimal
les palyndromes sur {a,b}
les expressions régulières sur {a,b}
la "théorie de l'ordre alphabétique" (exemples de théorèmes : arbre<mouche, balle<ballerine)

Exercice 4. Grammaire -> schéma d'induction

Comment définir par un schéma d'induction le langage engendré par le grammaire

S->aSb, S->R, R->bRa, R->e ?

Retour