Scribd
Importer
271 vues2 pages

Automates à Pile et Langages Formels

Cet exercice propose quatre exercices sur les automates à pile. Le premier exercice demande d'analyser un automate à pile donné et de trouver d'autres automates reconnaissant certains langages. Le deuxième exercice concerne une grammaire et la construction d'automates à pile équivalents. Le troisième exercice demande de construire des automates à pile à partir d'une grammaire sous forme normale de Greibach. Le quatrième exercice analyse une grammaire non-contextuelle.

Transféré par

Mouhamed Rassoul Gueye
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
271 vues2 pages

Automates à Pile et Langages Formels

Cet exercice propose quatre exercices sur les automates à pile. Le premier exercice demande d'analyser un automate à pile donné et de trouver d'autres automates reconnaissant certains langages. Le deuxième exercice concerne une grammaire et la construction d'automates à pile équivalents. Le troisième exercice demande de construire des automates à pile à partir d'une grammaire sous forme normale de Greibach. Le quatrième exercice analyse une grammaire non-contextuelle.

Transféré par

Mouhamed Rassoul Gueye
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Université Nice Sophia Antipolis L3 Info, L3 Math-MI

Automates & Langages 2017–2018

TD no 8

Automates à pile

Exercice 1) Plaçons-nous sur l’alphabet Σ = {0, 1}. Voici la table de transition δ d’un automate à pile
A = (Q, Σ, Γ, δ, q0 , Z, {q2 }) avec Q = {q0 , q1 , q2 }, Γ = {X, Z}, q0 est l’état initial et q2 est l’unique état
final :

état lecture pile nouvel état à empiler


q0 0 Z q2 Z
q0 0 X q1 ε
q0 1 Z q0 ZX
q0 1 X q0 XX
q1 0 Z q2 Z
q1 0 X q1 ε
q2 0 ε q2 ε

1. L’automate A est-il déterministe ?


2. Quel est le langage algébrique LF (A) reconnu par l’automate à pile A précédent, la reconnaissance se faisant
sur état final ?
3. Quel serait le langage L∅ (A) reconnu par A si la reconnaissance avait lieu sur pile vide ?
4. Trouvez un automate à pile B pour reconnaître le langage L∅ (B) = LF (A).

Exercice 2) Considérons la grammaire G suivante :

Grammaire G
Axiome = S
N = {S}
T = {0, 1}
P = { S → 0S0 | 1S1 | ε }

1. Quel est le langage engendré par G ?


2. Trouvez un automate à pile pour reconnaître le langage L(G).
3. Est-il déterministe ?
4. Soit G′ la grammaire obtenue en remplaçant dans G la production S → ε par S → 2. Trouvez un automate à
pile déterministe pour reconnaître L(G′ ).

Exercice 3) Considérons la grammaire G suivante, elle est donnée sous Forme Normale de Greibach :

Grammaire G
Axiome = S
N = {S, A, B}
T = {a, b}
P = { S → aB | bA
A → a | aS | bAA
B → b | bS | aBB }
1. Rappelez quel est le langage engendré par cette grammaire.
2. En utilisant la méthode du cours, construisez directement à partir de cette grammaire un automate à pile
reconnaissant le langage L(G) ?
3. Trouvez à présent de façon intuitive un autre automate à pile pour ce langage.

Exercice 4) Voici une grammaire G qui n’est pas non-contextuelle :

Grammaire G
Axiome = A
N = { A, B, C }
T = { a, b, c }
P={ A → aABC
A → aBC
CB→ BC
aB → ab
bB → bb
bC → bc
cC → cc }

1. Quel est le langage L(G) engendré par la grammaire G ?


2. Donnez un exemple de la suite de dérivations permettant d’obtenir un mot de L(G) à partir de l’axiome A. On
choisira un mot de longueur supérieure ou égale à 4.

Exercice complémentaire

Exercice 5) Plaçons-nous sur l’alphabet Σ = {0, 1}. Voici la table de transition δ d’un automate à pile A =
({q0 , q1 , q2 }, Σ, {X, Y, Z}, δ, q0 , Z, ∅). A reconnaît sur pile vide.

état lecture pile nouvel état à empiler


q0 0 Z q1 X
q0 1 Z q1 Y
q1 0 ε q1 X
q1 1 ε q1 Y
q1 ε X q2 X
q1 ε Y q2 Y
q2 0 X q2 ε
q2 1 Y q2 ε

1. L’automate à pile A est-il déterministe ? Justifiez.


2. Quel est le langage algébrique L∅ (A) reconnu par l’automate à pile A sur pile vide ?

Vous aimerez peut-être aussi