Scribd
Importer
12 vues1 page

Exercices sur les Automates et Langages

Transféré par

Mø Hã Męd
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
12 vues1 page

Exercices sur les Automates et Langages

Transféré par

Mø Hã Męd
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é de Bouira Faculté des sciences et des sciences appliquées

RATTRAPAGE S3 Théorie des langages Mr HAMID - R


Documentation non autorisée 2° A Informatique 07 février 2015 Durée 01H30

Exercice N°01 (06,00 pts)

On considère l’automate non-déterministe A de la figure suivante :


b
a
S0 S1 S2
ɛ
a b
FIG. – Automate non-déterministe A
1. Construire l’automate déterministe (A') équivalent à (A) .
2. Construire une grammaire régulière G telle que L(G) = L(A).

Exercice N°02 (5,00 pts)

Construire l'automate de Robin Scott (AEF) qui accepte le langage dénoté par l'expression:

e = (a|b)*a(a|b)*
Indication
 | désigne l' union U .

 Propriétés des dérivées

– ∪ || ∪ || .

– e1.e2||u = (e1||u). e2 | f(e1).( e2||u) tel que f(e1) = {ɛ} si ɛ ∈e1 et f(e1) = Ф sinon.
– (e*)||u = (e||u)e*.

Exercice N°03 (5,00 pts)

Soit le langage T = {aibj | i <> j}


1. Montrer que T est un langage hors contexte en fournissant une grammaire hors contexte qui l’engendre.
2. A partir de la grammaire proposée trouver un automate à pile qui accepte T.
3. Quel est le langage a*b* − T ?

Indication: trouver d’abord les grammaires engendrant { aibj | i < j } et { aibj | i > j }

Exercice N°04 (4,00 pts)

soit le langage {anbncn, n >= 0}

Trouver une grammaire G engendrant ce langage. Quel est son type (0, 1, 2 ou 3) ? Existe-t-il un automate
d'états fini déterministe reconnaissant ce langage ? Si oui lequel ?

Good luck

Vous aimerez peut-être aussi