Langages et automates Flashcards
Définition d’un alphabet
Ensemble fini non vide dont les éléments sont appelés des lettres
Définition d’un mot sur l’alphabet A
Suite finie (éventuellement vide pour le mot vide ε) de lettres de A
Définition de Aⁿ, A* et A⁺
Aⁿ ensemble des mots sur A, de longueur n
A* ensemble des mots de l’alphabet A (A* = ∪Aⁿ)
A⁺ = A* \ ε (ensemble des mots de longueur non nulle)
Définition d’un langage sur A
Un langage sur A est un sous ensemble de A*, donc un ensemble de mots sur A
Définition de facteur d’un mot, cas particulier d’un suffixe et d’un préfixe
v est un facteur du mot m sur A, s’il existe des mots u et w sur A tels que m = uvw
Si u = ε alors v est un préfixe et si w = ε alors v est un suffixe
Opérations sur les langages (9 opérations différentes)
K et L deux langages sur A. On définit les langages suivants :
union : K ∪ L = K + L
intersection : K ∩ L
complémentation : ¬L = A* \ L
différence ensembliste : K \ L
différence symétrique : KΔL = (K \ L) ∪ (L \ K)
concaténation : K.L = {uv | u∈K, v∈L}
puissance n : Lⁿ = L.Lⁿ⁻¹ avec L⁰ = ε
itération (opération étoile) : L* = ∪Lⁿ
opération plus : L⁺ = L* \ ε = L.L = L.L
Opérations rationnelles :
Union, concaténation, opération étoile. Par extension : puissance et plus
Expression rationnelle sur l'alphabet A Langage rationnel (ou régulier)
Expression arithmétique obtenue à partir de ε, ∅, lettres de A et A ainsi que d’opérations rationnelles.
Un langage est rationnel s’il peut être décrit par une expression rationnelle. L’ensemble des langages rationnels sur l’alphabet A est noté Rat(A*)
Définition d’un automate fini sur un alphabet A
C’est un quadruplet M = (E, T, I, F) pour lequel :
E est un ensemble fini dont les éléments sont appelés états (en général 1, 2…)
T est un sous ensemble de E × A × E, dont les éléments sont les transitions entre états
I est la partie de E formée des états initiaux
F est la partie de E formée des états acceptants (finaux, terminaux)
Définition d’un automate fonctionnel
Un automate est fonctionnel si pour chaque état, il n’y a qu’une seule transition partant de l’état et étiquetée par la même lettre.
Définition d’un chemin réussi
Il relie un état initial à un état acceptant
Exemple de langages non reconnaissables
{aⁿbⁿ | n∈ℕ}
{aⁿ | n premier}
Langage des palindromes sur {a; b}
Pour montrer qu’un langage L n’est pas reconnaissable, on raisonne par l’absurde :
1) on suppose qu’il est reconnaissable par un automate à N états
2) on choisit un mot suffisamment long pour en déduire une boucle dans l’automate permettant de fabriquer de nouveaux mots reconnus mais n’appartenant pas à L
Théorème de Kleene
L’ensemble des langages reconnaissables sur A est exactement l’ensemble des langages rationnels
Rec(A) = Rat(A)
Définition d’un automate complet
Un automate M est dit complet sur l’alphabet A si pour tout état e de M et toute lettre a de A, il existe une transition de e vers un autre état e’, étiquetée par a.
Graphiquement : de tout état de M, pour toute lettre a de A, part une flèche étiquetée par a.
Complétion d’un automate M
Si M n’est pas complet, on lui ajoute un état puits non acceptant vers lequel plongent toutes les transitions manquantes. Ce nouvel automate et l’ancien sont équivalents.
