^{PDFprof.com Search Engine}

Théorie des Langages Rationnels

Comment montrer qu'un langage est rationnel ?
Un mot donné appartient-il à un langage rationnel : il suffit de tester si le mot est reconnu par l'automate.
Le langage rationnel est-il vide : pour cela, on teste si, parmi les états accessibles, figure un état final.
Le langage contient-il tous les mots : il suffit de tester si le complémentaire est vide.
Comment prouver qu'un langage est régulier ?
On dit qu'une expression régulière dénote ou décrit un langage. (a+ε) (ba) *(b+ε) décrit l'ensemble des suites alternées de a et de b.
Un langage est régulier si et seulement si il est dénoté par une expression régulière.
Comment savoir si un automate est déterministe ?
Un automate fini et déterministe est complet si et seulement si δ est une application de Q × Σ sur Q.
De chaque état, il part alors exactement un arc étiqueté par chacune des lettres de l'alphabet Σ.
Quand la fonction n'est pas une application, l'automate fini peut se trouver bloqué.
Soit (Q, q0, F, δ) un automate fini deterministe : — Un blocage de l'automate est un couple (q, x) ∈ Q × s tel que δ(q, x) n'est pas défini. — Un automate sans blocages est dit complet. — L'automate est dit standard si pour tout (q, x) ∈ Q × s , δ(q, x) ̸= q0.

Un langage rationnel sur un alphabet X est un sous-ensemble de X∗ défini inductive- ment de la façon suivante : — ∅ et {ε} sont des langages rationnels ; — pour tout a ∈ X, le singleton {a} est un langage rationnel ; — pour tous g et h rationnels, les ensembles g ∪ h, g.h et g∗ sont des langages rationnels.

THL (Théorie des langages) Notes de cours
Langages rationnels et automates finis Exemples et applications
THLR

Théorie des Langages Rationnels

Comment montrer qu'un langage est rationnel ?

Comment prouver qu'un langage est régulier ?

Comment savoir si un automate est déterministe ?