Scribd
Importer
140 vues2 pages

TD 9

Le document présente plusieurs exercices sur les automates à pile et les grammaires algébriques. Les exercices portent sur la nature de langages engendrés par des grammaires données, et sur la construction d'automates à pile reconnaissant ces langages.

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
140 vues2 pages

TD 9

Le document présente plusieurs exercices sur les automates à pile et les grammaires algébriques. Les exercices portent sur la nature de langages engendrés par des grammaires données, et sur la construction d'automates à pile reconnaissant ces langages.

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 9

Automates à pile (suite)

Exercice 1) Considérons à nouveau la grammaire non-contextuelle suivante :

Grammaire G
Axiome = S
N = {S }
T = {0, 1}
P={ S→0|0S
S→1SS|S1S|SS1 }

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


2. Passez directement de G à un automate à pile reconnaissant L(G). On ne vous demande pas de
mettre cette grammaire sous Forme Normale de Greibach. Adaptez seulement la méthode vue en
cours à une grammaire algébrique sous une forme quelconque.

Exercice 2) Considérons la grammaire G suivante :

Grammaire G
Axiome = S
N = {S, A, B, C, D}
T = {a, b}
P={ S →CD
C →aCA
C →bCB
AD→aD
BD→bD
Aa →aA
Ab →bA
Ba →aB
Bb →bB
C →ε
D →ε }

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


2. Quelle est la nature de ce langage L(G) (rationnel, algébrique ou non-algébrique) ?
3. Quelle est la nature de son complémentaire L(G) ?
4. Si L(G) est algébrique, donnez un automate à pile ou une grammaire algébrique pour ce langage.
Exercices complémentaires

Exercice 3) Considérons la grammaire G suivante :


Grammaire G
Axiome = S
N = {S, X, Y, Z, B}
T = {a, b, c, d}
P={ S →XY }
X →aXc | aZc
Y →BYd | Bd
cB →Bc
bB →Bb
ZB→Zb
Z →ε
1. Cette grammaire G est-elle algébrique ? Pourquoi ?
2. Quel est le langage engendré par cette grammaire ? Est-il algébrique ?

Exercice 4) La classe des langages algébriques n’est pas close par intersection. Cependant, l’intersection
d’un langage algébrique et d’un langage rationnel est algébrique. Il peut se produire également que l’inter-
section de 2 langages algébriques non-rationnels soit algébrique. Donnez un exemple d’un tel couple de
langages.

Vous aimerez peut-être aussi