^{PDFprof.com Search Engine}

CHAPITRE 1 : EXPRESSIONS REGULIERES ET AUTOMATES

Comment savoir si un langage est régulier ?
Théorème (Kleene 1951) : un langage est régulier si et si seulement il existe un automate à nombre fini d'états le reconnaissant.
Dans la suite, on va voir comment on peut passer de l'expression régulière à l'automate et vice versa.
Quel est le langage reconnu par l'automate de la figure ?
Le mot w appartient au langage reconnu par l'automate si il existe un chemin de l'état initial à un état final qui décrit ce mot. e est un mot du langage reconnu par l'automate si l'état initial est final.
Comment montrer qu'un langage n'est pas régulier ?
Exemple : Soit L représenté par (ab + ba)*a et h(0) = aa, h(1) = aba.
On peut utiliser ces théorèmes pour montrer que certains langages ne sont pas réguliers.
Exemple : Soit L l'ensemble des mots ayant deux fois plus de a que de b.
Si L était régulier, il en serait de même de L ∩ a*b* = {a2nbn : n ≥ 0}.
Il existe une autre méthode pour construire l'automate union pour qu'à partir de deux automates déterministe, cet automate union soit, lui aussi, déterministe.
Soit T₁={A₁, Q₁, I₁, F₁, μ₁} et T₂={A₂, Q₂, I₂, F₂, μ₂} deux automates déterministes et complets.

Comment savoir si un langage est régulier ?