Exercices automates finis et expressions rationnelles T...

Théorie des langages : Exercices automates finis et expressions rationnelles

Télécharger PDF

Feuille d’exercices : Automates finis et expressions rationnelles

Informatique Théorique 2 - Unité J1INPW11

Licence 3 - Université Bordeaux 1

Exercice 1

Langage associé à une expression régulière

Donner tous les mots de tailles 0, 1, 2, 3 et 4 des langages réguliers suivants :

1. (a + ba)∗

2. a(aa + b(ab)∗a)∗a

Exercice 2

Expression régulière d’un langage

Sur l’alphabet {a, b}, donner une expression régulière pour :

1. Le langage des mots qui contiennent un nombre pair de b entre deux occurrences de a.

2. Le langage des mots tels que toutes les occurrences de a précèdent toutes les occurrences de b.

Exercice 3

Langage reconnu par un automate

Donner tous les mots de longueurs 0, 1, 2, 3 et 4 reconnus par les automates des figures 1 et 2.

Exercice 4

De l’automate à la définition mathématique

Pour les automates des figures 1 et 2, donner leurs définitions mathématiques.

Exercice 5

De la définition mathématique à l’automate

Pour chacune des deux définitions mathématiques suivantes, dessiner l’automate qui les représente.

Automate A3

Q = {1, 2, 3}, q_i = 1, F = {2, 3}, δ :

(1, a) → 2
(1, b) → 2
(2, c) → 2
(2, a) → 3
(3, b) → 1

Automate A4

Q = {1, 2, 3}, q_i = 2, F = {2}, δ :

(1, a) → 1
(1, b) → 2
(3, a) → 3
(2, b) → 1

Exercice 6

Quelques exemples d’automates

Donner, si possible, un automate et une expression régulière pour les langages suivants construits sur l’alphabet {a, b, c} :

Tous les mots.
Tous les mots sans b.
Tous les mots contenant au plus une occurrence de la lettre a.
Tous les mots contenant au moins une occurrence de la lettre a.
Tous les mots dans lesquels chaque a est suivi d’un b.
Pour un mot donné x, {x} (langage contenant uniquement x).
Tous les mots de longueur paire.
Tous les mots avec le préfixe ab.
Tous les mots avec le suffixe ab.

Démontrer que les automates donnés reconnaissent bien ces langages et que les expressions régulières les décrivent.

Exercice 7

Exercice plus difficile et recommandé en travail personnel

Étant donné un alphabet A et un mot x de A∗, construire un automate déterministe à |x| + 1 états qui reconnaît A∗x.

Exercice 8

Quelques identités sur les langages

Soient K et L deux langages et L⁺ = Lⁱ pour i > 0. Est-ce que les identités suivantes sont correctes ? Justifier vos réponses.

L⁺ = LL∗
LL∗ = L∗
L∗ = ε + LL∗
(KL)∗K = K(LK)∗

Exercice 9

Expression régulière d’un automate

Donner sous forme d’expressions régulières les langages reconnus par les automates des figures 1 et 2. Calculer ces expressions régulières avec deux méthodes différentes (algorithme de résolution des équations, l’algorithme de McNaughton et Yamada, etc.).

Exercice 10

Automate d’une expression régulière

À l’aide de l’algorithme de Glushkov, donner des automates finis (sans transitions ε) qui reconnaissent les langages suivants :

aa(a + ab)∗b
(a + ab)∗(ε + ab)
aab(ab)∗ + ab∗ + a∗bba
a((ab)∗c(b∗)∗)∗ + a(ababacb∗)∗a∗

Exercice 11

Automate déterministe ou non déterministe ?

Les automates suivants sont-ils déterministes ou non déterministes ? Pourquoi ?

Automate A5 (Figure 3)
Automate A6 (Figure 4)

Donner des exemples d’automate déterministe et non déterministe.

Exercice 12

Déterminisation d’un automate

Proposer un automate non déterministe qui reconnaît les mots qui se terminent par ab. Déterminiser cet automate.
Déterminiser les automates de l’exercice 11.

FAQ

1. Qu’est-ce qu’un automate déterministe ?

Un automate déterministe est un automate fini où chaque transition est unique pour un état donné et un symbole d’entrée. Cela signifie qu’il ne peut y avoir qu’une seule transition possible à partir d’un état pour un symbole donné.

2. Comment construire un automate reconnaissant uniquement un mot x ?

Un automate reconnaissant uniquement le mot x peut être construit avec un chemin unique passant par tous les symboles de x, et un état initial unique. L’état final est l’état atteint après avoir lu x.

3. Qu’est-ce que l’algorithme de Glushkov ?

L’algorithme de Glushkov permet de construire un automate fini sans transitions ε à partir d’une expression régulière donnée.