MP/MP* option TD Automates Q.
Fortier
I Algorithme de déterminisation
Déterminiser l’automate suivant en utilisant l’algorithme du cours :
a
1 2
a a
b
3 4 b
b
II Clôture des langages reconnaissables
Si m = m1 ...mn est un mot, on définit son miroir m
e = mn ...m1 . Si L est un langage, on définit son miroir L
e = {m
e | m ∈ L}.
1. Montrer que le miroir d’un langage reconnaissable est reconnaissable.
Si L est un langage sur Σ, on définit :
• P ref (L) = {u ∈ Σ∗ | ∃v ∈ Σ∗ , uv ∈ L} : ensemble des préfixes des mots de L.
• Suf f (L) = {u ∈ Σ∗ | ∃v ∈ Σ∗ , vu ∈ L} : ensemble des suffixes des mots de L.
• F act(L) = {u ∈ Σ∗ | ∃v, w ∈ Σ∗ , vuw ∈ L} : ensemble des facteurs des mots de L.
2. Montrer que si L est reconnaissable alors P ref (L), Suf f (L), F act(L) le sont aussi.
3. Montrer que si L est rationnel alors P ref (L), Suf f (L), F act(L) le sont aussi (puisqu’on va montrer que rationnel =
reconnaissable, c’est une preuve alternative à la précédente).
III Reconnaissable ou non ?
Pour chacun de ces langages, dire s’il est reconnaissable ou non. Justifier.
1. L1 = mots sur {a, b} sans lettres consécutives égales.
2. L2 = mots sur {a, b} ayant un nombre pair de a et dont le nombre de b est multiple de 3.
3. L3 = {m ∈ {a, b}∗ | |m|a = |m|b } (où |m|a est le nombre de a du mot m).
4. L4 = écritures en base 2 des multiples de 5.
5. L5 = {ap | p est un nombre premier}.
IV Algorithmes sur les automates
1. À quelle condition nécessaire et suffisante simple le langage reconnu par un automate est vide? Décrire un algorithme pour
le savoir.
2. À quelle condition nécessaire et suffisante simple le langage reconnu par un automate est fini? Décrire un algorithme pour
le savoir.
3. Décrire un algorithme pour déterminer si deux automates admettent le même langage.
4. Soit A un automate à n états. Montrer que si L(A) est non vide alors il contient un mot de longueur ≤ n − 1.
5. On dit qu’un automate est émondé si, pour tout état q, il existe d’une part un chemin d’un état initial à q et d’autre part
un chemin de q à un état final. Montrer que tout automate est équivalent à un automate émondé.
V Longueur discriminante
1. Soit A un automate. Décrire un algorithme pour déterminer la plus petite longueur d’un mot reconnu par A et préciser sa
complexité.
2. Soit A un automate à n états et de langage L(A). Montrer que L(A) = ∅ si et seulement si L(A) ne contient aucun mot
de longueur strictement inférieure à n.
3. Soit A1 = (Q1 , i1 , F1 , δ1 ) et A2 = (Q2 , i2 , F2 , δ2 ) deux automates déterministes complets à n1 et n2 états et de langages L1
et L2 . On suppose que L1 6= L2 . Soit l(L1 , L2 ) la plus petite longueur d’un mot u appartenant à l’un des deux langages
mais pas à l’autre.
Montrer que l(L1 , L2 ) < n1 n2 .
VI Ensemble distingant
Soient L un langage sur un alphabet Σ et u, v ∈ Σ∗ . On dit que w ∈ Σ∗ est un suffixe distingant pour u et v si exactement l’un
des mots uw ou vw appartient à L.
Un ensemble de mots D est distingant pour L si toute paire de mots de D a un suffixe distingant.
1. Soit L1 le langage dénoté par l’expression régulière (ab)∗ . Montrer que {ε, a, b} est un ensemble distingant pour L1 .
2. On note ind(L) le nombre minimum d’états d’un automate déterministe complet reconnaissant L. Montrer que si L a un
ensemble distingant de taille n alors ind(L) > n.
3. Que vaut ind(L1 ) ?
4. On suppose que L a un ensemble distingant infini. Montrer que L n’est pas un langage régulier.
5. En déduire que {an bn | n ∈ N} n’est pas un langage régulier.
6. Soit L2 l’ensemble des mots de {a, b}∗ qui contiennent un nombre pair de a et un nombre pair de b. Déterminer ind(L2 ).
VII Oral ENS info
On fixe un alphabet Σ avec |Σ| > 1. Un mot w ∈ Σ∗ est un palindrome s’il s’écrit w = a1 · · · an et qu’on a ai = an−i+1 pour tout
1 ≤ i ≤ n. On note Π ⊆ Σ∗ le langage des palindromes. Pour un automate fini A sur Σ, on note L(A) le langage reconnu par A.
1. Soit Πn := Π ∩ Σn . Montrer que pour tout automate fini déterministe complet A, pour tout n ∈ N, si L(A) ∩ Σ2n = Π2n ,
alors A a au moins |Σ|n états.
2. En déduire que le langage Π n’est pas régulier.
3. Étant donné un automate fini A sur Σ, peut-on calculer un automate AΠ qui reconnaisse L(A) ∩ Π?
4. Pour tout mot u = b1 · · · bm de Σ∗ , on note u := bm · · · b1 son miroir. Étant donné A, peut-on calculer un automate A0Π
qui reconnaisse {u ∈ Σ∗ | uu ∈ L(A)} ?
5. On appelle Πpair l’ensemble des palindromes de longueur paire, i.e., Πpair = Π2n . Proposer un algorithme qui, étant
[
n∈N
donné un automate fini A sur Σ, détermine si L(A) ∩ Πpair est vide, fini, ou infini. Discuter de sa complexité en temps et
en espace.
6. Modifier l’algorithme de la question 4 pour calculer la cardinalité de L(A) ∩ Πpair quand cet ensemble est fini, en faisant
l’hypothèse que l’automate d’entrée A est déterministe. Comment la complexité est-elle affectée?
7. Modifier l’algorithme des questions 4 et 5 pour qu’il s’applique à L(A) ∩ Π.
