diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 63 |
1 files changed, 52 insertions, 11 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index efb4a57..6312c88 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2084,7 +2084,7 @@ choix. \section{Langages reconnaissables et langages rationnels}\label{section-recognizable-languages} -\subsection{Stabilité des langages reconnaissables} +\subsection{Stabilité des langages reconnaissables par opérations booléennes et miroir} \thingy On rappelle qu'on a défini un langage \index{reconnaissable (langage)}reconnaissable comme un langage $L$ pour lequel il existe @@ -2213,12 +2213,15 @@ chaque état $q$ et chaque lettre $x$, il existe une unique arête aboutissant à $q$ et étiquetée par $x$ — sont parfois dits « co-déterministes ».) +\subsection{Stabilité des langages reconnaissables par opérations rationnelles, automates standards} + \thingy Nous allons maintenant montrer que la classe des langages reconnaissables est stable par les opérations rationnelles (union, concaténation et étoile de Kleene, -cf. \ref{stable-under-rational-operations} ; on l'a déjà vu pour la -réunion, mais on va en donner une nouvelle démonstration, qui a un -contenu algorithmique utile dans des circonstances différentes). +cf. \ref{stable-under-rational-operations} ; on l'a déjà vu sur les +DFA en \ref{dfa-union-and-intersection} pour la réunion, mais on va en +donner une nouvelle démonstration, cette fois basée sur les NFA, qui a +un contenu algorithmique utile dans des circonstances différentes). Pour établir ces stabilités, on va travailler sur les NFA et utiliser la construction parfois appelée « de Glushkov » ou « automate @@ -2567,6 +2570,29 @@ final dans cet automate $A'$ consiste en un nombre quelconque dans $A$. On a donc bien $L_{A'} = L^*$. \end{proof} +\thingy\label{trivial-standard-automata} Il sera utile de fixer +également des NFA (« standards » au sens de +\ref{standard-automaton-lemma}) reconnaissant les langages de base +triviaux $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour +chaque $x\in\Sigma$). On prendra les suivants : + +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$}; +\end{tikzpicture} +pour le langage $\varnothing$\\ +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial,final] {$q_0$}; +\end{tikzpicture} +pour le langage $\{\varepsilon\}$\\ +\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)] +\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$}; +\node (q1) at (60bp,0bp) [draw,circle,state,final] {$q_1$}; +\draw [->] (q0) to node[auto,swap] {$x$} (q1); +\end{tikzpicture} +pour le langage $\{x\}$. +\end{center} + \begin{cor}\label{rational-languages-are-recognizable} Tout langage rationnel est reconnaissable ; de plus, un NFA le reconnaissant se déduit algorithmiquement d'une expression rationnelle @@ -2577,9 +2603,9 @@ algorithmiquement si un mot vérifie une expression rationnelle.) Cela résulte de façon évidente de la définition des langages rationnels (cf. §\ref{subsection-rational-languages}), du fait que les langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour -chaque $x\in\Sigma$) sont reconnaissables par automates finis, et des -propositions \ref{nfa-union}, \ref{nfa-concatenation} -et \ref{nfa-star}. +chaque $x\in\Sigma$) sont reconnaissables par automates finis +(cf. \ref{trivial-standard-automata}), et grâce aux propositions +\ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}. Pour décider si un mot vérifie une expression rationnelle, on peut commencer par transformer cette expression rationnelle en NFA standard @@ -2590,10 +2616,25 @@ automate en DFA quitte déterminiser si l'automate accepte le mot. \end{proof} -\textcolor{red}{TODO: Standardiser la construction des automates. Par - exemple, utiliser le NFA « standard » ou « de Glushkov » (ayant un - seul état initial, éventuellement final, sans aucune transition qui - y mène).} +\thingy Les constructions que nous avons décrites dans cette section +associent naturellement un NFA standard à chaque expression +rationnelle : il s'obtient en partant des automates décrits +en \ref{trivial-standard-automata} et en appliquant les constructions +décrites dans les démonstrations de \ref{nfa-union}, +\ref{nfa-concatenation} et \ref{nfa-star}. Cette automate standard, +parfois appelé automate « de Glushkov », possède les propriétés +suivantes : +\begin{itemize} +\item c'est un NFA reconnaissant le langage $L_r$ dénoté par + l'expression rationnelle $r$ dont on est parti, +\item il est standard au sens de \ref{standard-automaton-lemma}, + c'est-à-dire qu'il possède un unique état initial qui n'est la cible + d'aucune transition, +\item son nombre d'états est égal à $1$ plus le nombre de lettres (à + l'exclusion des métacaractères) contenues dans l'expression $r$. +\end{itemize} + +\textcolor{red}{TODO: Développer, et donner des exemples.} \subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)} |