L'essentiel de la théorie des langages

Thèmes abordés

Informatique, Théorie des languages, language informatique, étoile de Kleene, état final, sciences appliquées, NFA Nondeterministic Finite Automaton, automate fini déterministe, DFA Deterministic Finite Automaton, automate fini non déterministe, transition, état non final, puissance d'un langage, monoïde, concaténation d'un langage, état puits

Résumé du document

Ce document comporte un cours de mathématiques-informatique, portant sur la théorie des langages.

Extraits

[...] si n = 0 alors  = ϵ ∈ A. Absurde sinon  = 1 2 3  n ,  ∈ . ∀,  ∈  ⊂ A ⇒  ∈ A. Absurde Donc : ∗est un monoïde libre Morphismes Définition 1.12 Un morphisme d'un monoïde M dans un monoïde N est une application φ : ϵM ) 7→ ϵN ) telle que : • φ(ϵM ) = ϵN : l'image de l'élément neutre de M est l'élément neutre de N. [...]

[...] Extension de la fonction de transition ∗ 4.3 Langage Reconnu par un NFA . Proposition 4.4 Conversion d'un NFA à un DFA 4.5 Proposition Chapter NFA à transitions vides (ε − NFA) . ε − NFA 5.2 Cloture d'un état q . Extension de * 5.4 Langage reconnu par un ε − NFA . Proposition . Règles de passage d'un ε − NFA vers un NFA . Conséquence . Minimisation d'un DFA .6 Passage d'une expression régulière à un ε − NFA .6. [...]

[...] Soit M = ∗, q un DFA Créer deux ensembles d'états : A = F et B = Q − F ∈ et deux états q et qj d'une même classe tel que δ(q , ) et δ(qj, ) n'appartiennent pas à la même classe alors créer une nouvelle classe et séparer les deux états q et q j. On laisse dans la même classe tous les états qk dont δ(qk, ) appartiennent à la même classe P pour tout ∈ .      Répéter 2 jusqu'à ce qu'il n'y ait plus d'états à séparer.  . S'il existe un symbole  4. L'état initial du DFA résultant est la classe P qui contient q    Exercice 5.1  fi 5 ′  . [...]

[...] Les flèches peuvent être étiquetées par des éléments de ∗ • Si r = ε, r = r =  évident • B ∈ ER() 7→ A + AB, A∗ ∈ ER() Département : Mathématiques et informatique 23 Ecole Nationale des Sciences Appliquées d'Al Hoceima CHAPTER . NFA À TRANSITIONS VIDES (ε − NFA) PROPRIÉTÉS DES LANGAGES RÉGULIERS Exemple 5.5 R = ( + b)∗ ( + bb)( + b)∗ Propriétés des langages réguliers Reg() est fermé par les opérations suivantes : • ∪ , l'union. • l'intersection. • la concaténation. • ∗, fermeture de Kleene. • Complémentation :  ∗ ∖L. • Différence L1 ∖ L ˜ • Mirroir L. [...]

[...] • A = A∗ = 2N Un monoïde E est dit libre s'il admet une partie génératrice A telle que chaque élément de E se décompose de façon unique en éléments de A. Département : Mathématiques et informatique 7 Ecole Nationale des Sciences Appliquées d'Al Hoceima CHAPTER 1. PRÉLIMINAIRES RAPPELS SUR LES MONOÏDES Propriété 1.2 (∗ est un monoïde libre (engendré par ).  ϵ    ■      Preuve. Montrer d'abord que ( ∗ ) est un monoïde (évident). Montrons que ∗est le plus petit sous monoïde engendré par . [...]