Langages réguliers et automates finis
Langages réguliers et automates finis
Programming, Math, etc. · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente les notions fondamentales des langages réguliers et des automates finis, destinées aux étudiants en informatique ou en mathématiques théoriques. Il couvre la définition des langages réguliers, la construction d'automates finis déterministes et non déterministes, ainsi que des exercices illustrant ces concepts.
Soit un alphabet fini !.
Les cas de base des langages réguliers sont :
Soient L et K des langages réguliers, alors :
Soit l'alphabet ! = {0, 1} :
Ce langage correspond à l'ensemble des mots composés d'un nombre arbitraire de 1, suivis de 01, puis d'un nombre arbitraire de 0.
Un automate fini M est défini par la structure M = (Q, !, $, q0, F) où :
Propriété importante : si R est un langage régulier, alors il existe un automate fini M tel que L(M) = R.
Considérons l'alphabet ! = {0, 1} :
Ce langage correspond à l'ensemble des nombres binaires impairs, qui se terminent nécessairement par 1.
1. Tout langage fini est régulier :
2. Le langage L = {0n1n | n ≥ 0} n'est pas régulier :
Construire un NFA acceptant les chaînes qui se terminent par 00 sur l'alphabet ! = {0, 1} :
Technique : construction par sous-ensembles (subset construction).
Soit un NFA N = (QN, !, $N, q0, FN), on construit un DFA D = (QD, !, $D, {q0}, FD) où :
Soit un "-NFA E = (Q, !, $E, q0, F), on construit un NFA N = (Q, !, $N, q0, F) tel que :
Soit un NFA avec états {p, q, r, s} et transitions :
La construction du DFA donne des états sous forme de sous-ensembles, par exemple :
Les transitions sont déterminées par l'union des transitions des états composants.
Exemple d'automate acceptant des chaînes sur l'alphabet ! = {A, B, C, ..., Z} :
char buffer; // Initialise au 1er caractère de l’input
char next_char() {
return buffer;
}
void read_next() {
buffer = getchar();
}
bool alpha(char c) {
return (c >= 'A' && c <= 'Z');
}
int automate() {
int state = 8;
char c;
while (true) {
switch (state) {
case 8:
if (next_char() == 'W') state = 4;
else if (next_char() == 'I') state = 9;
else if (alpha(c)) state = 3;
else state = 8;
read_next();
break;
case 4:
// ...
case 2:
if (alpha(c)) state = 3;
else return 2; // Pas de read_next!
read_next();
break;
}
}
}