Skip to main content

Automates, Applications finies

📄️ Langages non réguliers

Au chapitre précédent, nous avons étudié les langages réguliers. Nous avons particulièrement montré que les langages réguliers. Ainsi donc, le problème de décision $\omega \in L$ peut être résolu par un automate fini uniquement si $L$ est un langage régulier. Il se pose donc la question de l'existence de langages non réguliers. Nous allons tout d'abord montrer l'existence de tels langages, puis nous donnons une condition nécessaire pour qu'un langage soit régulier. La négation de cette condition nécessaire donne une condition suffisante pour qu'un langage ne soit pas régulier, et donc pour prouver l'irrégularité.

📄️ Grammaires

Un automate fini est une description analytique d'un langage régulier elles explicitent des règles de construction des mots du langage. Nous connaissans déjà la notion de grammaires en lagage naturel. Par exemple, en français, une phrase déclarative à la forme : "sujet" + "verbe" + "complément". La grammaire a pour rôle de fixer la structure des phrases. En informatique, les grammaires sont couramment utilisées pour définir la syntaxe des langages de programmation et pour construire les compilateurs.

Objectif du cours​

Les automates finis permettent de modéliser des programmes informatiques à mémoire finie. Ils permettent de résoudre des problèmes à un niveau d'abstraction élevé, sans s'encombrer des spécificités d'un langage donné, et en se concentrant sur les invariants à maintenir pour parvenir à une solution.

L'enseignement aborde des notions théoriques (automates finis, langages réguliers, expressions régulières, équivalence de ces trois formalismes, non-déterminisme, automate minimal, lemme de l'étoile) ainsi que leur utilisation pour la résolution de problèmes concrets.

Ressources pédagogiques​

Le support de cours

ThèmeSujet de TD
Automates finis et languagetd1-sujet
Expressions régulières et théorème de Kleenetd2-sujet
Langages non régulierstd3-sujet
Grammairestd4-sujet
Non déterminisme et déterminisationtd5-sujet
Automate minimal et minimisationtd6-sujet
Introduction à l'analyse lexicaletd7-sujet
0%