\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Définition


Soient \( \A\) un AEF\( \varepsilon\) , \( \sigma\in\Sigma_\A^*\) tel que \( \norm{\sigma}=n\) . On dira que \( \sigma\) est accepté par \( \A\) si il existe une suite \( e_0, e_1, \dots, e_n\) de \( E_\A\) tel que
  1. \( e_0\in I_\A\) ,
  2. \( e_n\in F_\A\) ,
  3. \( \forall k\in [\![1,n]\!], \ \tau_\A(e_{k-1},\sigma_k)=e_{k}\)
Autrement dit : un mot de longueur \( n\) est accepté par un automate s'il existe un chaine de longueur \( n-1\) dans le graphe représentant l'automate ayant un état initial pour origine et un état final pour aboutissement.

Exemple


\[\xymatrix@C=2cm{ \ar[d]&\\ p\ar@/^2pc/[r]^0\ar@(ld,lu)[]^1\ar[d] &i\ar@/^2pc/[l]^0\ar@(rd,ru)[]_1\\ & } \] Les mots \( \varepsilon\) , \( 001\) , \( 100\) , \( 1100\) , \( 010\) sont acceptés par l'automate ci-contre.

Définition


Le langage d'un AEF\( \varepsilon\) \( \A\) est l'ensemble des mots acceptés. \[L(\A)=\left\{\sigma\in\Sigma_\A^*\Big| \sigma \text{ est accepté par }\A\right\}\]

Exemple


\[\xymatrix@C=2cm{ \ar[d]&\\ p\ar@/^2pc/[r]^0\ar@(ld,lu)[]^1\ar[d] &i\ar@/^2pc/[l]^0\ar@(rd,ru)[]_1\\ & } \] Les mots reconnus par cet automate sont tous les mots de \( \{0,1\}\) possédant un nombre paire de \( 0\) .

Définition


Soient \( \Sigma\) un alphabet et \( L\subset \Sigma^*\) un langage. On dira que \( L\) est un langage d'états finis, s'il existe un ADEF \( \A\) tel que \( \Sigma=\Sigma_\A\) et \( L(\A)=L\) . On dit que l'automate \( \A\) reconnait le langage \( L\) .

Exemple


Considérons l'alphabet \( \Sigma=\{0,1,2,3,4,5,6,7,8,9\}\) et le langage \( L=\N\) des nombres. Il s'agit d'un langage d'états finis. En effet les nombres (ne commençant pas par \( 0\) sauf \( 0\) lui même) sont reconnus par l'A(D)EF suivant : \[ \xymatrix@C=3cm{ &\ar[d]&\\ &\varnothing\ar[rd]^0\ar[ld]_{1,\dots,9}&\\ Vrai\ar[d]\ar@(ld,lu)[]^\Sigma&Faux\ar@(ld,rd)[]_\Sigma&0\ar[d]\ar[l]^\Sigma\\ &&\\ } \]

Théorème [Rabin-Scott]


Soit \( \A\) un AEF. \[L(\A)=L(\A_{det})\]

Démonstration

Admise
Il est parfois plus naturel de construire une AEF qui traduit un langage puis de le déterminer (et le compléter) pour pouvoir le programmer.

Exemple


Considérons l'AEF qui reconnait les mots de l'alphabet \( \Sigma=\{a,b\}\) qui se termine par \( bab\) : \[ \xymatrix{ \ar[r]& 0\ar[r]^b\ar@(lu,ru)[]^a\ar@(ld,rd)[]_b& 1\ar[r]^a& 2\ar[r]^b& 3\ar[r] &} \] Le déterminé (complété) de cet AEF est \[ \xymatrix{ \ar[r]& A\ar[r]^b\ar@(lu,ru)[]_a& B\ar[r]^a\ar@(lu,ru)[]_b& C\ar@/^1pc/[r]^b\ar@/_2pc/[ll]_a& D\ar[r]\ar@/^2pc/[ll]^b\ar@/^1pc/[l]_a& &} \]

Théorème


Soit \( \A\) un AEF\( \varepsilon\) . \[L(\A)=L(\A_\varepsilon)\]

Démonstration

Admise.

Exercice


Décrire un automate déterministe et complet permettant de reconnaitre les langages suivants.
  1. Les mots finissant par \( bab\) sur l'alphabet \( \Sigma=\{a,b\}\) .
  2. Les mots commençant par \( aba\) sur l'alphabet \( \Sigma=\{a,b\}\) .
  3. Les mots ne contenant pas de \( 00\) sur l'alphabet \( \Sigma=\{0,1\}\) .
  4. Les nombres entiers (\( \N\) ) sur \( \Sigma=\{0,1,2,3,4,5,6,7,8,9\}\) .
  5. Les nombres entiers paires (\( 2\N\) ) sur \( \Sigma=\{0,1,2,3,4,5,6,7,8,9\}\) .
  6. Les nombres entiers divisible par 3 (\( 3\N\) ) sur \( \Sigma=\{0,1,2,3,4,5,6,7,8,9\}\) .
  7. Les entiers relatifs (\( \Z\) ) sur l'alphabet \( \Sigma=\{0,1,2,3,4,5,6,7,8,9,-\}\) .
  8. Les expressions mathématiques correctes sur l'alphabet \( \Sigma=\{0,1,2,3,4,5,6,7,8,9,+,-\}\) .