Td langages formels frederic gruau Théorie des langages...

Théorie des langages : Td langages formels frederic gruau

Télécharger PDF

Langages Formels 2019-2020

TDs + devoir + TP

Plan du cours

Le cours est divisé en six périodes de deux semaines, avec l’enchaînement des six thèmes suivants :

• a- Rappels
• b- Approfondissement automates
• c- Grammaires Hors Contexte
• d- Automates à piles
• e- Analyse syntaxique ascendante
• f- Machine de Turing

L’enchaînement est une construction logique, c’est-à-dire qu’il est nécessaire d’assimiler les concepts au fur et à mesure pour pouvoir continuer jusqu’au bout. En particulier, les élèves n’ayant jamais vu d’expressions rationnelles ni d’automates d’états finis doivent fournir un effort considérable les deux premières semaines (rappels) pour se mettre à niveau avec le reste.

Organisation des cours et TD

Il y a 12 cours (1h30) suivis de 12 TD (2h). Le cours prépare aux TDs. Le déroulement pour chacune des 12 semaines est le suivant :

a- Rappels

• Cours : Panorama des langages formels, expressions rationnelles, lemme d’Arden, définition des automates d’états finis.
• TD : Égalité des langages, expressions rationnelles, automates simples.

b- Approfondissement automates

• Cours : Automates non-déterministes, transitions epsilon, théorème de Kleene.
• TD : Automates, suite et fin, déterminisation, résolution d’équations (début).

c- Grammaires Hors Contexte

• Cours : Grammaires hors contexte, arbre de dérivation, ambiguïté, réécriture droite.
• TD : Grammaire d’un langage, langage d’une grammaire, désambiguïsation.

d- Automates à piles

• Cours+TD : Automates à piles, TD est-il-algébrique (suite).
• Cours : Équivalence automate à pile-grammaire, clôture, premier et suivant.
• TD : Est-il-algébrique (fin), analyse ascendante à la main, premier et suivant.

e- Analyse Ascendente

• Cours+TD : Analyse ascendante.
• Cours : Automates LR(1) général, LALR(1), introduction à la machine de Turing.
• TD : Exercices d’analyse ascendante (rappel + LR, LALR), machine de Turing simple.

f- Machine de Turing

• Cours : Décidabilité, TD machine de Turing compliquée, décidabilité de l’ambiguïté.
• Cours : NP-complétude, TP en salle avec yacc et lex.

Les exercices optionnels sont plus difficiles et conçus pour occuper les meilleurs étudiants ou vous permettre de travailler chez vous. Certains exercices plus importants ou plus difficiles sont répartis sur deux TDs : le premier TD traite un exemple facile, et le TD de la semaine suivante un deuxième exemple plus difficile.

C’est le cas pour les automates d’états finis (TD 1 et 2), la résolution d’équations de langages (TD 2 et 3), est-il-algébrique (TD 6, 7 et 8), l’analyse ascendante (TD 9 et 10), et les machines de Turing (TD 10 et 11).

Examens, Devoirs, Rattrapage

Seules les notes de cours manuscrites et les polycopiés de cours et d’exercices sont autorisés aux examens. Chaque TD fait l’objet d’un exercice au partiel ou à l’examen. Le partiel et l’examen comprennent aussi des questions de cours non traitées en TD.

Les notes de partiels mauvaises pourront être partiellement rattrapées grâce à un devoir relativement facile, mais avec un coefficient de seulement 10 % par rapport au partiel. Le contrôle continu est calculé comme suit : (9 × partiel + devoir) / 10.

L’examen de rattrapage en juin porte sur toute l’année.

Démonstration d’égalité entre deux langages

Les égalités suivantes sont-elles vraies ? Si oui, le démontrer ; sinon, donner un contre-exemple.

1. L* = (L*)^*
2. L.(M ∩ N) = (L.M) ∩ (L.N)
3. Optionnel : (L*.M)^* = {ε}⁺ + (L + M)^*.M

Expression rationnelle

ExprRat d’un langage

Écrire une expression rationnelle pour les langages suivants :

1. L₁ = {w | w commence par a}
2. L₂ = {w | w termine par b}
3. L₃ = {w | w commence par ab et termine par bb}
4. L₄ = {w | w contient trois occurrences successives de la lettre a}
5. L₅ = {w | w ne commence pas par ba}
6. L₆ = {w | w ne termine pas par bba}

Optionnel : ExprRat complexe

Écrire une expression rationnelle pour les langages suivants :

1. L₇ = {w | w ne contient pas deux occurrences successives de la lettre a}
2. L₈ = {w | w ne contient pas trois occurrences successives de la lettre a}
3. L₉ = {w | le nombre de a dans w est pair} = {w | |w|_a = 0 (mod 2)}
4. L₁₀ = {w | le nombre de a dans w est congru à 1 modulo 3} = {w | |w|_a = 1 (mod 3)}

ExprRat pour l’analyse lexicale

La première étape d’un compilateur est l’analyse lexicale, qui découpe le texte d’un programme en unités lexicales appelées « tokens ». Un token peut être un mot-clé, un identifiant ou une constante numérique. On utilise des expressions rationnelles pour identifier la nature des différents tokens.

Écrire l’expression rationnelle décrivant :

1. Un identifiant comme une lettre suivie d’une suite de lettres ou de chiffres.
2. Un entier positif.
3. Un entier relatif.
4. Un nombre à virgule.

Automates reconnaissant un langage donné

Donner des automates reconnaissant les langages suivants : les entiers sont codés en binaire. Pour les entiers comme pour les mots habituels, on considère que les caractères sont lus de gauche à droite, donc en commençant par les bits de poids forts.

1. Des entiers pairs, des entiers impairs, des puissances de 2.
2. A = {0,1}, L = {w | w code une puissance de 4}.
3. A = {0,1}, L = {w | w code la somme de deux puissances de 4 distinctes : 4^k + 4^k', k ≠ k'}.
4. A = {a,b}, L = {w | w commence par abaaba}.
5. A = {a,b}, L = {w | w contient abaaab}.
6. A = {a,b}, L = {w | w commence par abb et termine par bba}.

Déterminisation

Méthode de déterminisation

Déterminiser les automates suivants :

1. Automate avec transitions a et b.
2. Automate avec transitions a, b, ab et ba.

Boum !

Soit L_n l’ensemble des mots sur {a,b} de longueur au moins n dont la n-ième lettre avant la fin est b. Donner un petit automate non-déterministe pour L₃, puis sa déterminisation. Comparer leur nombre d’états.

Résolution d’équations

Exemple à faire

À l’aide du système d’équations précédent, que l’on résoudra par élimination et utilisation du lemme d’Arden, déterminer une expression rationnelle correspondant aux automates suivants (sur l’alphabet A = {a,b}) :

1. Automate avec transitions ab, a, b.
2. Automate avec transitions ab, ab, a, b.

Exemple optionnel

Déterminer une expression rationnelle pour l’automate suivant :

1. Automate avec transitions ab, ab, ba, a, b.
2. Automate avec transitions a, b, ab, ba, b.

Construction d’automates

Construction classiques

L’automate A = (Σ, Q, δ, q₀, F) reconnaît le langage L. Construire des automates reconnaissant :

1. Le miroir de L : {a_na_n-1...a₃a₂a₁ | a₁a₂...a_n ∈ L}.
2. L’ensemble des mots obtenus à partir des mots de L en effaçant tous les a.
3. Le complémentaire de L, en supposant Σ déterministe.
4. Optionnel : L’ensemble des mots obtenus en effaçant un nombre pair de lettres d’un mot de L.

Produit synchronisé pour l’intersection

L₁ et L₂ sont reconnus par les automates A₁ et A₂.

On suppose que A₁ et A₂ sont déterministes complets.

1. Donner un algorithme linéaire en |u| pour savoir si u ∈ L₁ ∩ L₂.
2. En déduire la construction d’un automate déterministe reconnaissant l’intersection (produit synchronisé).
3. Construire également un automate déterministe reconnaissant l’union.

Optionnel : Adaptation aux automates non complets ou non-déterministes

Les constructions précédentes s’adaptent-elles aux automates non complets ou non-déterministes ?

Le barman boxeur

Un exercice ludique de Laurent Rosaz mettant en jeu des techniques de construction d’automate.

1. Donner un automate dont les états sont les différentes configurations du plateau, les lettres les coups annoncés par le barman, et où les flèches décrivent les évolutions possibles des configurations.
2. À partir de l’état où deux verres côte à côte sont dans un sens et les deux autres dans l’autre, donner une séquence de coups permettant au barman de gagner.
3. Donner un automate non-déterministe (avec éventuellement plusieurs états d’entrée) qui donne toutes