908 -- Automates Finis, exemples et applications

Plan d'Emmanuel et Ivan (2012)

Le Plan

On se place sur un alphabet fini $\Sigma$.

I - Automates finis et langages reconnaissables

I.1 - Définitions et Propriétés

1. Définitions : Automates finis, calcul/chemin, mots acceptés, langages reconnu par un AF, $Rec(\Sigma ^{*})$, AF complet, émondé, à epsilon transitions, déterministe.
2. Thm : tout AF peut etre émondé, complété, déterminisé, desespsilonisé.
   • Exemples de chaque type et leurs images par le théorème.
   • Remarque : tout déterminisé d'un AF a au plus $2^{n}$ états.
3. Prop : Problème du vide et problème du mot sont décidables
   • Complexité en $Nlogspace$.

I.2 - Propriétés de clôtures et lemme d'itération

1. Lemme de l'étoile
2. Propriétés de clôture de $Rec(\Sigma ^{*})$

II - Langages Rationnels

1. Déf : $Rat(\Sigma ^{*})$
2. Thm de Kleen
3. exemples : $\{a^{n}b^{n},n\geq 0\}$

III - Automate minimal

But : ${\mathcal {A}}$ AF, trouver ${\mathcal {A}}'$ AFDC de même langage et minimal pour le nombre d'état

1. Déf et prop sur les quotients à gauches
   • Déf, prop classiques
   • Thm : l'automate minimal est l'automate des quotients
   • Prop : caract des langages rationnels par la finitude de l'ensemble des quotients à gauche
2. Congruence de Nérode
   • Déf congruence
   • Déf congruence de Nérode
   • Prop : l'algo de Moore calcule la congruence de Nérode en ${\mathcal {O}}(|\Sigma ||Q|^{2})$.

IV - Applications ...

IV.1 - ... à la logique

1. Thm de Presburger [Dev 1]

IV.2 - ... à l'analyse lexicale

1. Définir les notions et insister sur la place de l'analyse lexicale dans la chaîne de compilation
2. Exemple si la place

IV.3 - à l'algorithmique du texte

1. Algo naïf de recherche d'un mot dans un texte + complexité
2. Algo par automate + complexité
3. Algo Morris et Pratt + complexité
4. Conclure sur le fait que les automates sont pas trop mal pour ce type de problème.

==== IV.4 - ... à la classification

1. Déf de la séparation de deux langages par un automate (PSA)
2. PSA est NP-Complet [Dev 2]

Développements possibles

• Thm de Presburger [Carton] - se place dans les leçons [908], [909] (moins), [914], [924]
• PSA est NP-Complet [Sakarovitch] - se place dans les leçons [908], [915]
• Thm de Kleen - se place dans les leçons [908], [909], autre ? - développement très peu innovant, les jury ne l'aiment pas.
• Congruence de Nérode
• Knuth-Morris-Pratt - je ne garanti pas qu'il soit faisable en développement mais si oui il se recase en algo du texte, et complexité.

Références

• Luc Albert - pour la quasi totalité du plan
• Carton - pour Presburger et compléments du plan
• Sakarovitch - Pour PSA est NP-complet - pas très lisible pour faire un plan
• David, Nour, Raffalli - Introduction à la logique - Pour les bases de la logique pour Presburger (pour les questions qui viendrons après)