DM de Langages Formels

Younesse Kaddar

Énoncé
Version PDF
[Link]

I. Automates à pile déterministes

Exercice 1

1.
R ∗
Lpal ≝ {w$w ∣ w ∈ {a, b} }

Pour abréger les notations, x dénotera un élément quelconque de l’alphabet de pile {A, B, ⊥}.

L’automate à pile Apal (tel que Σ ≝ {a, b, $}, Γ ≝ {A, B, ⊥} ) suivant :

a, x/xA | b, x/xB b, B/ | a, A/

$, x/x , ⊥/
⊥ q_0 q_1 q_f

reconnaît Lpal .

en effet :
on voit aisément que tout mot de Lpal est reconnu par Apal
et réciproquement : si w′ est reconnu par Apal , alors il existe γ tel que :
∗ ∗
∈ {a, b, $} ∈ Γ

w
q0 , ⊥ ⟶A qf , γ

Or, la seule transition allant en qf est (q1 , ⊥, ε, qf , ε), où ⊥ est le fond de pile. Donc γ = ε .
On peut ensuite remarquer qu’au cours de l’exécution de Apal sur w , le nombre de transitions effectuées de q0 à
′

q0 est égal au nombre de transitions de q1 à q1 .

en effet : toutes les transitions de l’état q0 dans lui-même ajoutent un symbole sur la pile, la transition de q0 à
q1 laisse la pile inchangée, et toutes les transitions de q1 dans lui-même suppriment un symbole la pile.
Comme la pile est initialisée avec le fond de pile ⊥, lequel est supprimé de q1 à q2 , le résultat s’ensuit.
Il vient donc, par définition de Apal , que
w
q0 , ⊥ ⟶A qf , γ

est de la forme :
w1 w2 wi

q0 , ⊥ ⟶A q0 , γ ⟶A ⋯ ⟶A q0 , γ ⎞
1 i

$ ⎟
⟶A q1 , γ ⎟
i
⎟
wi+1 wi+2 w2i ⎟
′ ′ ⎟⊛
⟶A q1 , γ ⟶A ⋯ ⟶A q1 , γ
1 i ⎟
 ⎟
⎟
=⊥ ⎟

ε
⎠
⟶A qf , ε

où ∀j, wj ∈ {a, b}

Montrons que w′ est de la forme :

R
w$w

où w ∈ {a, b}
∗
, par induction sur la taille (impaire) de w′ .
si |w′ | = 1 : alors w′ = $ nécessairement, et le résultat est acquis.
si w′ ≝ w1 ⋯ wi $wi+1 ⋯ w2i (où i ≥ 1 ∧ ∀j, wj ∈ {a, b} , par ⊛) et |w| > 1 :
⊛
 ≝ ⊛

Par ⊛, et comme les transitions de q0 dans lui-même ne font qu’ajouter un symbole au-dessus du sommet de
la pile, et les transitions de q1 dans lui-même ne font que supprimer le symbole de sommet de pile, on a :
w2 w3 wi

q0 , ⊥ ⟶A q0 , ζ ⟶A ⋯ ⟶A q0 , ζ
1 i ⎞

$ ⎟
⟶A q1 , ζ ⎟
i
⎟
wi+1 wi+2 w2i−1 ⎟
q1 , ζ
′
⋯ q1 , ζ
′
⎟ ⊛ ⊛
⟶A ⟶A ⟶A
1 i ⎟
 ⎟
⎟
=⊥
⎟
ε
⎠
⟶A qf , ε

(avec w2 ⋯ wi , wi+1 ⋯ w2i−1 éventuellement vides) : le premier symbole ajouté sur la pile est le dernier
enlevé.
Donc w2 ⋯ wi $wi+1 ⋯ w2i−1 ∈ L(Apal ) , et par hypothèse d’induction :

R
wi+1 ⋯ w2i−1 = (w2 ⋯ wi )

Supposons maintenant que w1 = a . Par définition de Apal , A est le premier symbole ajouté (au-dessus du
fond de pile) : par ⊛, il apparaît donc (d’après les considérations précédentes) qu’il a été enlevé par la
transition

w2i
′ ′
q1 , γ ⟶A q1 , γ
i−1 i

=⊥

d’où, par construction de Apal :

w2i = a

On montre de même que si w1 ,

= b w2i = b , donc dans tous les cas : w1 = w2i , et :

′ R R
w ≝ w1 w2 ⋯ wi $(w2 ⋯ wi ) w2i = w1 w2 ⋯ wi $(w2 ⋯ wi ) w1

R
= w1 w2 ⋯ wi $(w1 w2 ⋯ wi )

et le résultat est acquis.

En outre, on vérifie aisément que Apal est déterministe, donc :

Lpal ≝ {w$w
R ∗
∣ w ∈ {a, b} } est déterministe.

2.
R +
Lh ≝ {w$(h(w)) ∣ w ∈ Σ }

Pour abréger les notations, x dénotera un élément quelconque de l’alphabet de pile Σ ∪ {⊥}.

On pose

Apal ≝ ⟨{q0 , q1 , qf }, Σ ∪ Δ ∪ {$} , Σ ∪ {⊥} , δ, q0 , ⊥, {qf }⟩

 

alphabet d'entrée alphabet de pile

où :

δ ≝ {(q0 , x, a, q0 , xa) ∣ a ∈ Σ}

∪ {(q0 , x, $, q1 , x)}

∪ {(q1 , a, h(a), q1 , ε) ∣ a ∈ Σ}

∪ {(q1 , ⊥, ε, qf , ε)}

∀a∈ : a, x/xa ∀a∈ : h(a), a/

$, x/x , ⊥/
⊥ q_0 q_1 q_f

reconnaît Lpal .

en effet :
on voit aisément que tout mot de Lpal est reconnu par Apal
et réciproquement : si w′ ∈ Σ ∪ Δ ∪ {$} est reconnu par Apal , on montre de la même manière que dans la
question précédente qu’on a :
w
 w
q0 , ⊥ ⟶A qf , ε

w
Et que q0 , ⊥ ⟶A qf , ε est de la forme :

w1 w2 wi

q0 , ⊥ ⟶A q0 , γ ⟶A ⋯ ⟶A q0 , γ
1 i ⎞

$ ⎟
⟶A q1 , γ ⎟
i
⎟
wi+1 wi+2 w2i ⎟
q1 , γ
′
⋯ q1 , γ
′ ⎟⊛
⟶A ⟶A ⟶A
1 i ⎟
 ⎟
⎟
=⊥
⎟
ε
⎠
⟶A qf , ε

où ∀j, wj ∈ Σ ∪ Δ

Montrons que w′ est de la forme :

R
w$(h(w))

où w , par induction sur la taille (impaire) de w′ .

+
∈ Σ

si |w′ | = 1 : alors w′ = $ nécessairement, et le résultat est acquis.

si w′ ≝ w1 ⋯ wi $wi+1 ⋯ w2i (où i ≥ 1 ∧ ∀j, wj ∈ Σ ∪ Δ , par ⊛) et |w| > 1 :
Par ⊛, et comme les transitions de q0 dans lui-même ne font qu’ajouter un symbole au-dessus du sommet de
la pile, et les transitions de q1 dans lui-même ne font que supprimer le symbole de sommet de pile, on montre
exactement de la même manière que dans la question précédente (avec l’hypothèse d’induction) que :

R
wi+1 ⋯ w2i−1 = (h(w2 ⋯ wi ))

Si w1 ≝ a ∈ Σ :
Par définition de Apal , a ∈ Σ est le premier symbole ajouté (au-dessus du fond de pile) : par ⊛, il apparaît
donc qu’il a été enlevé par la transition
w2i
′ ′
q1 , γ ⟶A q1 , γ
i−1 i

=⊥

Dans δ, la seule transition allant de q1 dans q1 et qui remplace a ∈ Σ par ε est (q1 , a, h(a), q1 , ε). Donc :

w2i = h(a) = h(w1 )

Par suite :

′ R
w = w1 w2 ⋯ wi $(h(w2 ⋯ wi )) w2i

R
= aw2 ⋯ wi $(h(w2 ⋯ wi )) h(w1 )

R
= w1 w2 ⋯ wi $(h(w1 )h(w2 ⋯ wi ))

R
= w1 w2 ⋯ wi $(h(w1 w2 ⋯ wi )) (car h est un morphisme)

Si w1 ≝ d ∈ Δ :
Dans δ, les seules transitions qui étiquetées par des lettres (de l’alphabet d’entrée) appartenant à Δ vont
de q1 à q1 .
Donc la transition
w1

q0 , ⊥ ⟶A q0 , γ
1

ne peut pas avoir lieu, ce qui contredit ⊛. Ce cas est donc exclus.
Dans tous les cas, le résultat est acquis.

En outre, Apal est déterministe, puisque :

1. La seule ε-transition est (q1 , ⊥, ε, qf , ε), et il n’existe aucune autre transition depuis q1 , ⊥

2. Pour tous q ∈ {q0 , q1 , qf }, z ∈ Σ ∪ {⊥} , b ∈ Σ ∪ Δ ∪ {$} , il existe au plus une transition depuis q, z en lisant b :
 
alphabet de pile alphabet d'entrée

Si q = q0 :
si b ∈ Σ : La seule transition applicable est (q0 , z, b, q0 , zb).
si b ∈ Δ ou b = $ : aucune transition n’est applicable.
Si q = q1 :
si b ∈ Σ : aucune transition n’est applicable.
si b ∈ Δ : si z ∈ Σ et b = h(z) , la seule transition applicable est (q1 , z, h(z), q1 , ε).
Sinon : aucune transition n’est applicable.
si b = $ : la seule transition applicable est l’ε-transition précédemment citée
 Si q = qf : aucune transition n’est applicable.

On a donc montré que

Lh ≝ {w$(h(w))
R
∣ w ∈ Σ
+
} est déterministe.

3.
Soit L un langage régulier. Montrons qu’il est déterministe hors-contexte.

L est reconnu par un automate

A ≝ ⟨Q, Σ, δ, q0 , F ⟩

qu’on peut supposer déterministe et sans ε-transition, quitte à le déterminiser (avec l’automate des parties par exemple).

L’idée est cet automate peut être vu comme un automate à pile qui n’utilise pas sa pile : si on pose

′
AP DA ≝ ⟨Q, Σ, {⊥}, δ , q0 , ⊥, F ⟩

avec

′ ′ ′
δ ≝ {(q, ⊥, a, q , ⊥) ∣ (q, a, q ) ∈ δ}

On vérifie aisément que :

L’automate A et l’automate à pile AP DA reconnaissent le même langage (i.e L) :

en effet : tout mot reconnu par A est clairement reconnu par AP DA , et réciproquement, puisque la pile de AP DA reste
inchangée.

L’automate AP DA hérite du déterminisme de A :

en effet : Pour tous (q, z = ⊥, b) ∈ Q × {⊥} × Σ , le déterminisme de A implique qu’il existe au plus une transition de
la forme (q, b, q (où q ) dans δ; donc, par construction de δ , il existe au plus une transition de la forme
′ ′ ′
) ∈ Q

(où q ′ ) dans δ .
′ ′
(q, z, b, q ) ∈ Q

Par ailleurs, il n’existe pas d’ε-transition.

On a donc montré que

Tout langage régulier est déterministe hors-contexte.

Exercice 2
Soit L un langage hors-contexte.

Montrons que

il existe un DPDA A ≝ ⟨Q, Σ, Γ, δ, q0 , z0 ⟩ tel que L = N (A) si, et seulement si L est déterministe et préfixe.

⟹ :
Supposons qu’il existe un DPDA A ≝ ⟨Q, Σ, Γ, δ, q0 , z0 ⟩ tel que L = N (A) .

Montrons que L est déterministe et préfixe.

L est déterministe
On construit, de la même manière que dans le cours, l’automate à pile suivant :
′ ′
A ≝ ⟨Q ⊔ {qf }, Σ, Γ ⊔ {⊥}, δ , q0 , ⊥z0 , {qf }⟩

où

′
δ ≝ δ ∪ {(q, ⊥, ε, qf , ε) ∣ q ∈ F }
 '

q_3
, ⊥/

, ⊥/
⊥z_0 ⋯ q_2 q_f
, ⊥/

q_1

NB : on rajoute un nouveau fond de pile ⊥, et pour chaque q ∈ Q tel que la pile est “vide” (avec notre nouveau fond), on
ε
ajoute l’ε-transition q, ⊥ ⟶ qf , ε

On a démontré en cours que

′
L(A ) = N (A)

′
De plus, A est clairement déterministe, puisque pour tous (q, z)) ∈ Q ⊔ {qf } × Γ ⊔ {⊥} :

si q = qf : aucune transition ne part de q

sinon, si q ∈ Q :
si z ∈ Γ : les transitions partant de (q, z) sont celles de A, qui est déterministe.
′
si z = ⊥ : la seule transition qui part de (q, ⊥) est l’ε-transition (q, ⊥, ε, qf , ε) ∈ δ

Donc L est déterministe.

L est préfixe
Si n’était pas le cas, il existerait un mot w ≝ w1 w2 ∈ L avec w1 ∈ L .

de longueur ≥1

Par conséquent, comme L = N (A) , il existerait q1 , q1′ , q2 ∈ Q tels que :

w1
⎧q ,z ⟶
0 0 A q1 , ε (car w1 ∈ L)
⎨ w1 w2
⎩ ′ +
q0 , z 0 ⟶ A q , γ ⟶ A q2 , ε (car w2 ∈ L et |w2 | > 0)
1

Mais alors le déterminisme de A impliquerait :

′
q = q1
1
{
γ = ε

Et

w2
+
q1 , ε ⟶ A q2 , ε

devient alors absurde puisque qu’aucune transition ne peut partir de (q1 , ε), car la pile est vide.

Le résultat est donc acquis.

⟸ :
′
Supposons qu’il existe un DPDA A ′ ′ ′ ′
≝ ⟨Q , Σ , Γ , δ , q , z , F ⟩
′
0
′
0
′
reconnaissant L et que L est préfixe.

Montrons qu’il existe un DPDA A ≝ ⟨Q, Σ, Γ, δ, q0 , z0 ⟩ tel que L = N (A) .

Notons déjà qu’on peut supprimer toutes les transitions sortant d’un état final de A sans changer le langage reconnu
′

par A (qui reste L) puisque L est préfixe :

′

En effet : montrons que pour toute exécution de la forme

w
 w2
w1
′ ′ ′ ′ + ′ ′
q ,z ⟶A ′ q ,γ ⟶ A′ q ,γ (avec |w2 | > 0)
0 0 F F 2 2

′
∈F

nécessairement : w1 w2 ′
∉ L(A ) = L .
w1

Par l’absurde : si w1 w2 ′
∈ L(A ) = L , alors comme w1 ∈ L (puisque q0′ , z0′ ⟶A ′ q
′
F
,γ
′
F
) et |w2 | ,
> 0 L ne serait pas

′
∈F

préfixe.

′ ′
Pour ne pas alourdir les notations, on note encore A ′ ′
≝ ⟨Q , Σ , Γ , δ , q , z , F ⟩
′ ′
0
′
0
′
l’automate obtenu en supprimant toutes
les transitions sortant d’un état final.

On construit alors, de la même manière que dans le cours, l’automate à pile (qui accepte par pile vide) suivant :

′ ′ ′ ′ ′
A ≝ ⟨Q ⊔ {qf }, Σ , Γ ⊔ {⊥}, δ, q , ⊥z ⟩
0 0

où
′ ′ ′
δ ≝ δ ∪ {(q, z, ε, qf , ε) ∣ q ∈ F ⊔ {qf }, z ∈ Γ ⊔ {⊥}}

'

q_3'
, z/
, z/

, z/
⊥z_0' ⋯ q_2' q_f
, z/

q_1'

NB : on rajoute un nouveau symbole de fond de pile ⊥, et on ajoute des ε-transitions partant des anciens états finals vers
un nouvel état qf qui vide la pile.

On a démontré en cours que

′
N (A) = L(A ) = L

De plus, A est déterministe, puisque pour tous (q, z, b) ′

∈ Q ⊔ {qf } × Γ ⊔ {⊥} × Σ
′
:

si q = qf : la seule transition partant de (q, z) est l’ε-transition (qf , z, ε, qf , ε).

sinon, si q ∈ Q ∖F
′ ′
:
′
si z ∈ Γ
′
: les transitions partant de (q, z) sont celles de A , qui est déterministe.
si z = ⊥ : aucune transition ne part de (q, ⊥).
sinon, si q ∈ F
′
:
′
comme on a supprimé toutes les transitions sortant d’un état final dans A , la seule transition qui part de (q, z) est l’ε-
′
transition (q, z, ε, qf , ε) ∈ δ

Donc le résultat est acquis.

On a donc montré que

Pour tout langage hors-contexte L, il existe un DPDA A ≝ ⟨Q, Σ, Γ, δ, q0 , z0 ⟩ tel que L = N (A) si, et seulement si L
est déterministe et préfixe.
Exercice 3

1.
Comme on l’a vu en TD, l’automate A suivant (avec Σ ≝ {a, b}, Γ ≝ {A, B, ⊥} ) reconnaît
L ≝ {a b
n n
∣ n > 0} ∪ {a b
n 2n
∣ n > 0} :

b, A/

a, z/zA q_1 , ⊥/⊥

, */*

⊥ q_0 b, A/B | b, B/ q_3

, */* , ⊥/⊥

q_2

En effet :

Tout mot de L est clairement reconnu, et réciproquement, si w ≝ w1 ⋯ wm+n ∈ L(A) (où les wi ∈ {a, b} ):

soit l’exécution de A sur w passe par q1 :

Alors elle est de la forme :

w1 wm ε wm+1 wm+n ε
q0 , γ ⟶ ⋯ ⟶ q0 , γm ⟶ q1 , γm ⟶ ⋯ ⟶ q1 , γm+n ⟶ q3 , ⊥
0

=⊥

ε
Comme l’exécution est acceptante, elle se termine nécessairement par l’unique transition q1 , ⊥ ⟶ q3 ,⊥ , et


unique état final

la pile est dans le même état qu’au départ (il n’y a que le fond de pile) :

γ = ⊥ ⊛
m+n

Or :
toutes les transitions de q0 dans q0 empilent un A, et seulement à la lecture de la lettre a. Donc :

⎧ w1 = ⋯ = wm = a
⎪
i fois
⎨ 
⎩
⎪
∀i ∈ ⟦1, m⟧, γ = ⊥A ⋯ A (par une récurrence immédiate sur m)
i

l’unique transition de q0 vers q1 est une ε-transition qui laisse la pile inchangée
toutes les transitions de q1 dans q1 dépilent un A, et seulement à la lecture de la lettre b. Donc, de même (par une
récurrence immédiate sur n) :

⎧ wm+1 = ⋯ = wm+n = b
⎪
m−(i−m)=2m−i fois
⎨ 
⎩
⎪
∀i ∈ ⟦m + 1, m + n⟧, γ = ⊥ A⋯A ⊛ ⊛
i

l’unique transition de q2 vers q3 est une ε-transition qui la pile inchangée

Comme

⎧ ⊥ par ⊛
⎪
γ = ⎨⊥ A⋯A par ⊛ ⊛
m+n 
⎩
⎪
2m−(m+n)=m−n fois

Il vient que m − n = 0 , et

w = w1 ⋯ wn wn+1 ⋯ w2n ∈ L
 
n n
= a = b

soit l’exécution de A sur w passe par q2 :

Alors elle est de la forme :

w1 wm ε wm+1 wm+n ε
q0 , γ ⟶ ⋯ ⟶ q0 , γm ⟶ q2 , γm ⟶ ⋯ ⟶ q2 , γm+n ⟶ q3 , ⊥
0

=⊥

ε
 ε
Comme l’exécution est acceptante, elle se termine nécessairement par l’unique transition q2 , ⊥ ⟶ q3 ,⊥ , et

unique état final

encore une fois :

γ = ⊥ ⊛
m+n

Or :
On montre de même que précédemment que :

⎧ w1 = ⋯ = wm = a
⎪
i fois
⎨ 
⎩
⎪
∀i ∈ ⟦1, m⟧, γ = ⊥A ⋯ A
i

l’unique transition de q0 vers q2 est une ε-transition qui laisse la pile inchangée
toutes les transitions de q2 dans q2
remplacent le haut de la pile par un B si c’est un A
ou
dépilent le haut de la pile si c’est un B
et seulement à la lecture de la lettre b. Donc :

wm+1 = ⋯ = wm+n = b

Et

m−1 m−1
γ = ⊥A B γ = ⊥A
m+1 m+2

m−2 m−2
γ = ⊥A B γ = ⊥A
m+3 m+4

m−3 m−3
γ = ⊥A B γ = ⊥A
m+5 m+6

On montre ainsi par une récurrence immédiate sur n que :

m−i/2
⊥A si i est pair
∀i ∈ ⟦1, n⟧, γ = { ⊛ ⊛
m+i m−(i+1)/2
⊥A B sinon

l’unique transition de q2 vers q3 est une ε-transition qui la pile inchangée

Comme

γ = ⊥ par ⊛
m+n

et

m−n/2
⊥A si n est pair
γ = { par ⊛ ⊛
m+n m−(n+1)/2
⊥A B sinon

Il vient que n est pair et m − n/2 = 0 , d’où :

w = w1 ⋯ wm wm+1 ⋯ wm+2m ∈ L
 
m
= a 2m
= b

On a donc montré que

L ≝ {a b
n n
∣ n > 0} ∪ {a b
n 2n
∣ n > 0} est algébrique.

2.

a).
′
Soit w ∈ L(A ) .

Montrons que h(w) ∈ L(A) .

′
L’exécution de A sur w est de la forme :

w1 w2 wm

(q0 , 0), z0 ⟶A ′ (q1 , 0), γ ⟶A ′ ⋯ ⟶A ′ ( qm , 0), γ

1 m

∈F

g(wm+1 ) g(wm+2 ) g(wm+n )

⟶ A
′ (qm+1 , 1), γ ⟶ A
′ ⋯ ⟶ A
′ (qm+n , 1), γ
m+1 m+n

∈F
(puisque qu’il n’existe aucune transition allant d’un état de Q × {1} vers un état de Q × {0})

où

w = w1 ⋯ wm g(wm+1 ) ⋯ g(wm+n )

q0 , q1 , ⋯ , qm−1 ∉ F

qm ∈ F
′ ′
qm+n ∈ F puisque w ∈ L(A ) et l’ensemble des états finals de A est F × {1}

w1 , ⋯ , wm ∈ {a, b, ε}

wm+1 , ⋯ , wm+n ∈ {b, ε}

′
Par définition de δ , l’exécution
w1 w2 wm

q0 , z 0 ⟶ A q1 , γ ⟶A ⋯ ⟶A qm , γ
1 m

∈F

wm+1 wm+2 wm+n

⟶A qm+1 , γm+1 ⟶A ⋯ ⟶ A qm+n , γm+n


∈F

est acceptante dans A, et

w1 ⋯ wm ∈ L donc en particulier w1 , ⋯ , wm ∈ {a, b, ε}

{
w1 ⋯ wm+n ∈ L

Ainsi :

h(w) = h(w1 ) ⋯ h(wm )h(g(wm+1 )) ⋯ h(g(wm+n )) (car h est un morphisme)

= h(w1 ) ⋯ h(wm )wm+1 ⋯ wm+n (car h ∘ g = id)

= w1 ⋯ wm wm+1 ⋯ wm+n (car h∣{a = id et w1 , ⋯ , wm ∈ {a, b, ε} ) ∈ L

,b,ε}

Et le résultat est acquis.

b).
′
Soit w ∈ L(A ) .

On reprend les résultats et notations de la question précédente :

w = w1 ⋯ wm g(wm+1 ) ⋯ g(wm+n )

wm+1 , ⋯ , wm+n ∈ {b, ε}

donc g(wm+1 ), ⋯ , g(wm+n ) ∈ {c, ε}

w1 ⋯ wm ∈ L = L(A)

Il vient donc que

′ ′
w ≝ w w
1 2

où w′1 ∈ L(A), w
′
2
∈ {c}
∗

et le résultat est acquis.

d).
′
Soit w ∈ L(A ) .

D’après b) :

′ ′
w ≝ w w
1 2

′
w ∈ L(A) = L
1

donc en particulier : les lettres de w′1 appartiennent à {a, b}, et h(w′1 ) = w

′
1
puisque h∣{a,b} = id

′ ∗
w ∈ {c}
2

donc en particulier : h(w′2 ) ∈ {b}

∗
puisque h(c) = b

Et d’après a) :

′ ′ ′ ′
L ∋ h(w) = h(w )h(w ) = w h(w )
1 2 1 2
 
∗
∈L ∈{b}

Donc deux choses l’une :

′
 Soit w′2 = ε :
et

′
w = w ∈ L
1

Soit |w′2 | > 0 :

et comme

′ ′
w h(w ) ∈ L
1 2
 
+
∈L ∈{b}

il vient que il existe n > 0 tel que :

′ ′ n 2n
⎧ w h(w ) = a b ∈ L
⎪ 1 2
′ n n
⎨w = a b ∈ L
1
⎩
⎪ ′ n
h(w ) = b
2

Donc
′ ′ n n n
w = w w = a b c
1 2

Dans tous les cas :

n n n
w ∈ {a b c ∣ n > 0} ∪ L

et on a montré que :

′ n n n
L(A ) ∈ {a b c ∣ n > 0} ∪ L

3.
Soit n > 0 .

′
Montrons que an bn cn ∈ L(A ) .

Remarquons que

n n n n n n
a b c = a b g(b )

Or, comme

n 2n
a b ∈ L

n n
a b ∈ L

A est déterministe

il existe une unique exécution de A sur an b2n :

n n n
a b b
∗ ∗
q 0 , z0 ⟶ A
q1 , γ ⟶ A
q2 , γ ⊛
1 2
 
∈F ∈F

telle que

q1 (resp. q2 ) est le premier état final par lequel passe toute exécution acceptante de A sur an bn (resp. an b2n ) (A est
déterministe)
on prend cette précaution à cause de l’existence éventuelle d’ε-transitions dans A partant de q1 (resp. q2 ) dans
autre état final
n n
a b

il vient donc que, hormis q1 , aucun état par lequel passe l’exécution q0 , z0 ⟶
∗
A
q1 , γ
1
n’est final

De fait :
n n
a b

toute transition de q0 , z0 ⟶
∗
A
q1 , γ
1
est de la forme :

′
(q, z, d, q , γ) ∈ δ

où
d ∈ {a, b, ε}

q ∉ F
n
b

la première transition de q1 , γ1 ⟶
∗
A
q2 , γ
2
est de la forme :

′
 ′
(q, z, d, q , γ) ∈ δ

où
d ∈ {b, ε}

q = q1 ∈ F
n
b

les autres transition de q1 , γ1 ⟶

∗
A q2 , γ
2
sont de la forme :

′
(q, z, d, q , γ) ∈ δ

où
d ∈ {b, ε}

Donc l’exécution

les états appartiennent à Q×{0} les états appartiennent à Q×{1}

 
n n n n
a b g(b) =c
∗ ∗
(q0 , 0), z0 ⟶ A′ ( q1 , 0), γ ⟶ A′ ( q2 , 1)
1
 
∈F ∈F

obtenue à partir de ⊛ est bien définie et existe dans A ′

Comme (q1 , 1) est final dans A ′ , il en résulte donc que :

n n n ′
a b c ∈ L(A )

et le résultat est acquis.

n n n ′
{a b c ∣ n > 0} ⊆ L(A )

4.
D’après 2. c) et 3. :

n n n ′ n n n
{a b c ∣ n > 0} ⊆ L(A ) ⊆ {a b c ∣ n > 0} ∪ L

Donc en intersectant avec le langage régulier {a, b, c}∗ c :

n n n ∗ ′ ∗ n n n ∗ ∗
{a b c ∣ n > 0} ∩ {a, b, c} c ⊆ L(A ) ∩ {a, b, c} c ⊆ ({a b c ∣ n > 0} ∩ {a, b, c} c) ∪ (L ∩ {a, b, c} c)

 
n n n
= {a b c ∣n>0}
n n n
= {a b c ∣n>0} = ∅

Donc

′ ∗ n n n
L(A ) ∩ {a, b, c} c = {a b c ∣ n > 0}

Or

′
L(A ) ∩ {a, b, c} c
∗
est algébrique, en tant qu’intersection d’un langage algébrique et d’un langage régulier (d’après le
corollaire 1 de la section “Théorème de Bar-Hillel” du cours)

n
{a b c
n n
∣ n > 0} n’est pas algébrique (d’après l’EX 2. 1) du TD5) :
Supposons que L n
≝ {a b c
n n
∣ n ≥ 0} est algébrique.
Soit G = ⟨N , Σ, P , S⟩ telle que
L(G) = L

K est l’entier donné par le lemme d’Ogden, dont l’énoncé est rappelé ici.
Soit w = a
K
b
K
c
K
(où les a sont distingués, par exemple).
Il existe w = αuβvγ tq αun βvn γ ∈ L pour tout n, et u ≠ ε ou v ≠ ε (par le point c) du lemme d’Ogden).
Comme αu 2 2
βv γ ∈ L ⊆ a b c
∗ ∗ ∗
, u ne contient que des a ou que des b ou que des c, et de même pour v.
Or un des deux mots parmi u et v est non vide, et on n’a pas les trois lettres dans ces deux mots, donc
n
αu βv γ ∈ L
n
pour tout n, c’est absurde.

On obtient donc une contradiction, et :

L ≝ {a b
n n
∣ n > 0} ∪ {a b
n 2n
∣ n > 0} n’est pas déterministe.

Exercice 4
1.
Réduisons le complémentaire du problème de correspondance de Post au problème de l’intersection vide Pint_vide

On se donne une instance du problème de correspondance de Post :

ΣP ost un alphabet tel que ΣP ost ∌ $

n ∈ N
+
u1 , ⋯ , un ∈ Σ
P ost
+
v1 , ⋯ , vn ∈ Σ
P ost

Soit Σ un alphabet à n lettres a1 , ⋯ , an tel que

Σ ∩ (ΣP ost ∪ {$}) = ∅

On note hu (resp. hv ) le morphisme qui, à chaque ai , associe ui (resp. vi ).

On construit, de la même manière que dans l’exercice 1, deux automates à pile déterministes Au et Av reconnaissant
respectivement :

R +
Lu ≝ {w$(hu (w)) ∣ w ∈ Σ }

et

R +
Lv ≝ {w$(hv (w)) ∣ w ∈ Σ }

La fonction qui calcule ces deux automates est bien calculable.

De plus :

si l’instance du problème de correspondance de Post est positive :

il existe k ∈ ⟦1, n⟧ et des indices i1 , ⋯ , ik ∈ ⟦1, n⟧ tels que :

ui ⋯ ui = vi ⋯ vi
1 k 1 k

donc

hu (ai ) ⋯ hu (ai ) = ui ⋯ ui = vi ⋯ vi = hv (ai ) ⋯ hv (ai )

1 k 1 k 1 k 1 k

et

R
Lu ∋ ai1 ⋯ ai $(hu (ai1 ) ⋯ hu (ai ))
k k

R
= ai ⋯ ai $(hv (ai ) ⋯ hv (ai )) ∈ Lv
1 k 1 k

Donc Lu ∩ Lv ≠ ∅

Si Lu ∩ Lv ≠ ∅ :
Alors il existe :

R
Lu ∋ ai1 ⋯ ai $(hu (ai1 ) ⋯ hu (ai ))
k k

R
= aj ⋯ aj $(hv (aj ) ⋯ hv (aj )) ∈ Lv
1 r 1 r

Comme $ ∉ Σ :

a i 1 ⋯ a i k = a j1 ⋯ a jr
{
hu (ai1 ) ⋯ hu (aik ) = hv (aj1 ) ⋯ hv (ajr )

Donc k ,
= r (i1 , ⋯ , ik ) = (j1 , ⋯ , jk ) , et :

ui ⋯ ui = hu (ai ) ⋯ hu (ai ) = hv (aj ) ⋯ hv (aj ) = vi ⋯ vi

1 k 1 k 1 r 1 k

Donc l’instance du problème de correspondance de Post est positive.

On a montré que :

l’instance de problème de correspondance de Post est positive si, et seulement si l’instance (Lu , Lv ) de Pint_vide est
négative.

Soit :

l’instance de problème de correspondance de Post est négative si, et seulement si l’instance (Au , Av ) de Pint_vide est
positive, et
 On a réduit co − P CP , qui est indécidable, à Pint_vide : Pint_vide est donc indécidable.

2.

a).
On réduit Pint_vide à ce problème Pinclusion .

Soit (A1 , A2 ) une instance de Pint_vide (A1 , A2 sont des DPDA).

¯
¯¯¯
¯¯¯
On construit l’automate à pile déterministe A2 qui reconnaît Σ avec le théorème de clôture par complémentation.
∗
∖L(A2 )

La fonction qui calcule cet automate est bien calculable.

De plus :

∗ ¯
¯¯¯
¯¯¯
L(A1 ) ∩ L(A2 ) = ∅ ⟺ L(A1 ) ⊆ Σ ∖L(A2 ) = L(A2 )

d’où :

¯
¯¯¯
¯¯¯
(A1 , A2 ) est une instance positive de Pint_vide si, et seulement si (A1 , A2 ) est une instance positive de Pinclusion .

On a donc réduit Pint_vide , qui est indécidable, à Pinclusion : Pinclusion est donc indécidable.

b).
On réduit Pint_vide à ce problème Puniv .

Soit (A1 , A2 ) une instance de Pint_vide (A1 , A2 sont des DPDA).

¯
¯¯¯
¯¯¯ ¯
¯¯¯
¯¯¯
On construit les automates à pile déterministes A1 et A2 qui reconnaissent respectivement Σ et Σ , avec
∗ ∗
∖L(A1 ) ∖L(A2 )

le théorème de clôture par complémentation.

Puis, on construit l’automate à pile Aunion reconnaissant Σ (d’après l’EX 3. 3) du TD4), les langages
∗ ∗
∖L(A1 ) ∪ Σ ∖L(A2 )

algébriques sont clos par union).

La fonction qui calcule ces automates est bien calculable.

De plus :

∗ ∗
L(A1 ) ∩ L(A2 ) = ∅ ⟺ Σ ∖(L(A1 ) ∩ L(A2 )) = Σ

∗ ∗ ∗
⟺ Σ ∖L(A1 ) ∪ Σ ∖L(A2 ) = Σ

= L(Aunion )

d’où :

(A1 , A2 ) est une instance positive de Pint_vide si, et seulement si Aunion est une instance positive de Puniv .

On a donc réduit Pint_vide , qui est indécidable, à Puniv : Puniv est donc indécidable.