\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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} } \)
Accueil
Accueil
Connexion
Connexion
Liste des cours
Liste des cours
Exercices
Exercices
Projets
Projets
Département SD
Département SD
How To
How To
Au temps perdu
Au temps perdu

Considérons l'alphabet \( \Sigma=\{a, b, c\}\) et déterminons un automate reconnaissant la REGEX \( (a+b)c^*\) . Le parenthèsage permet d'identifier la priorité des calculs. Il nous faut donc
  1. Déterminer un automate reconnaissant \( a\)
  2. Déterminer un automate reconnaissant \( b\)
  3. En déduire un automate reconnaissant la somme \( a+b\)
  4. Déterminer un automate reconnaissant \( c\)
  5. En déduire un automate reconnaissant l'étoile \( c^*\)
  6. Finalement, en déduire un automate reconnaissant le concaténé \( (a+b)c^*\)
Pour les caractères nous pouvons utiliser la condition 3 : On note \( \A\) l'automate \[ \xymatrix{ \ar[r]&A\ar[rd]_{b, c}\ar[rr]^{a}&&B\ar[ld]^{a, b, c}\ar[r]&\\ &&C\ar@(ld, rd)[]_{a, b, c}&& } \] \[ \begin{array}{c|ccc} &a&b&c\\\hline \rightarrow A&B&C&C\\ B \rightarrow&C&C&C\\ C&C&C&C \end{array} \] On note \( \mathscr{B}\) l'automate \[ \xymatrix{ \ar[r]&A\ar[rd]_{a, c}\ar[rr]^{b}&&B\ar[ld]^{a, b, c}\ar[r]&\\ &&C\ar@(ld, rd)[]_{a, b, c}&& } \] \[ \begin{array}{c|ccc} &a&b&c\\\hline \rightarrow A&C&B&C\\ B \rightarrow&C&C&C\\ C&C&C&C \end{array} \] On note \( \mathscr{C}\) l'automate \[ \xymatrix{ \ar[r]&A\ar[rd]_{a, b}\ar[rr]^{c}&&B\ar[ld]^{a, b, c}\ar[r]&\\ &&C\ar@(ld, rd)[]_{a, b, c}&& } \] \[ \begin{array}{c|ccc} &a&b&c\\\hline \rightarrow A&C&C&B\\ B \rightarrow&C&C&C\\ C&C&C&C \end{array} \] Nous pouvons alors réaliser la somme \( \A+\mathscr{B}\) en utilisant les outils développés à la condition 4. \[ \begin{array}{c|ccc} & a&b&c\\\hline \rightarrow (A, A)& (B, C)& (C, B)& (C, C)\\ (A, B) \rightarrow & (B, C)& (C, C)& (C, C)\\ (A, C)& (B, C)& (C, C)& (C, C)\\ (B, A)\rightarrow & (C, C)& (C, B)& (C, C)\\ (B, B)\rightarrow & (C, C)& (C, C)& (C, C)\\ (B, C)\rightarrow & (C, C)& (C, C)& (C, C)\\ (C, A)& (C, C)& (C, B)& (C, C)\\ (C, B)\rightarrow & (C, C)& (C, C)& (C, C)\\ (C, C)& (C, C)& (C, C)& (C, C)\\ \end{array} \] \[ \xymatrix@C=1.719cm@R=0.519cm{ &&& (A, B)\ar[ld]_{a}\ar[dd]^{b, c}\ar[r]&&&\\ && (B, C)\ar[lu]\ar[rd]^{a, b, c}&& (A, C)\ar@/_5pc/[ll]_{a}\ar[ld]_{b, c}&&\\ \ar[r]& (A, A)\ar[ru]^{a}\ar[rd]^{b}\ar[rr]^{c}&& (C, C)\ar@(d, dl)[]^{a, b, c}&& (B, B)\ar[ll]_{a, b, c}\ar[r]&\\ && (C, B)\ar[ld]\ar[ru]_{a, b, c}&& (C, A)\ar[lu]_{a, c}\ar@/^5pc/[ll]^{b}&&\\ &&& (B, A)\ar[uu]_{a, c}\ar[lu]_{b}\ar[r]&&& } \] On à présent l'automate \( \mathscr{C}^*\) en utilisant la construction \( 6\) . \[ \xymatrix{ \ar[r]&A\ar[d]\ar[rd]_{a, b}\ar[rr]^{c}&&B\ar[ld]^{a, b, c}\ar@/_2pc/[ll]_{\varepsilon}&\\ &&C\ar@(ld, rd)[]_{a, b, c}&& } \] de matrice \[ \begin{array}{c|cccc} &a&b&c&\varepsilon\\\hline \rightarrow A\rightarrow&C&C&B&\\ B &C&C&C&A\\ C&C&C&C& \end{array} \] d'\( \varepsilon\) -libéré \[ \begin{array}{c|ccc} &a&b&c\\\hline \rightarrow A\rightarrow&C&C&B\\ B \rightarrow &C&C&B, C\\ C&C&C&C \end{array} \] d'automate déterministe associé \[ \begin{array}{c|ccc} &a&b&c\\\hline \rightarrow \{A\}\rightarrow &\{C\}&\{C\}&\{B\}\\ \{B\} \rightarrow&\{C\}&\{C\}&\{B, C\}\\ \{C\}&\{C\}&\{C\}&\{C\}\\ \{B, C\}\rightarrow&\{C\}&\{C\}&\{B, C\} \end{array} \] En renommant les sommets, on arrive à l'automate \[ \begin{array}{c|ccc} &a&b&c\\\hline \rightarrow X\rightarrow &Z&Z&Y\\ Y \rightarrow&Z&Z&T\\ Z&Z&Z&Z\\ T\rightarrow&Z&Z&T \end{array} \] \[ \xymatrix{ &&&\\ \ar[r] &X\ar[u]\ar[r]^{a, b}\ar[rd]_{c}&Z\ar@(ru, rd)[]^{a, b, c}&\\ & &Y\ar[l]\ar[u]_{a, b}\ar[d]^{c}&\\ & &T\ar[r]\ar@/_2.19pc/[uu]_{a, b}\ar@(ld, rd)[]_c& } \] Finalement, on concatène l'automate \( \A+\mathscr{B}\) et \( \mathscr{C}^*\) par des \( \varepsilon\) -transition : \[ \xymatrix{ &&& (A, B)\ar[ld]_{a}\ar[dd]^{b, c}\ar@/^1.19pc/@*{[red]}[rrrdr]^{\color{red}\varepsilon}&&&&&&\\ && (B, C)\ar@*{[red]}@/^6pc/[rrrrr]^{\color{red}\varepsilon}\ar[rd]^{a, b, c}&& (A, C)\ar@/_5pc/[ll]_{a}\ar[ld]_{b, c}&&&X\ar[r]^{a, b}\ar[rd]_c\ar[u]&Z\ar@(ru, rd)[]^{a, b, c}&\\ \ar[r]& (A, A)\ar[ru]^{a}\ar[rd]^{b}\ar[rr]^{c}&& (C, C)\ar@(d, dl)[]^{a, b, c}&& (B, B)\ar[ll]_{a, b, c}\ar@*{[red]}[rru]^{\color{red}\varepsilon}&&&Y\ar[l]\ar[u]_{a, b}\ar[d]^{c}&\\ && (C, B)\ar@*{[red]}@/_9pc/[rrrrruu]_{\color{red}\varepsilon}\ar[ru]_{a, b, c}&& (C, A)\ar[lu]_{a, c}\ar@/^5pc/[ll]^{b}&&&&T\ar[r]\ar@/_2.19pc/[uu]_{a, b}\ar@(ld, rd)[]_c&\\ &&& (B, A)\ar[uu]_{a, c}\ar[lu]_{b}\ar@/_3.19pc/@*{[red]}[rrruuur]^{\color{red}\varepsilon}&&&&&& } \] Sa matrice est \[ \begin{array}{c|cccc} & a&b&c&\varepsilon\\\hline \rightarrow (A, A)& (B, C)& (C, B)& (C, C)&\\ (A, B) & (B, C)& (C, C)& (C, C)&X\\ (A, C)& (B, C)& (C, C)& (C, C)&\\ (B, A) & (C, C)& (C, B)& (C, C)&X\\ (B, B) & (C, C)& (C, C)& (C, C)&X\\ (B, C)& (C, C)& (C, C)& (C, C)&X\\ (C, A)& (C, C)& (C, B)& (C, C)&\\ (C, B) & (C, C)& (C, C)& (C, C)&X\\ (C, C)& (C, C)& (C, C)& (C, C)&\\\ X\rightarrow &Z&Z&Y&\\ Y \rightarrow&Z&Z&T&\\ Z&Z&Z&Z&\\ T\rightarrow&Z&Z&T& \end{array} \] L'\( \varepsilon\) -libéré est (on note simplement \( AB\) au lieu de \( (A, B)\) pour alléger les notations) \[ \begin{array}{c|ccc} & a&b&c\\\hline \rightarrow AA&BC&CB&CC\\ AB \rightarrow &BC, Z&CC, Z&CC, Y\\ AC&BC&CC&CC\\ BA \rightarrow &CC, Z&CB, Z&CC, Y\\ BB \rightarrow &CC, Z&CC, Z&CC, Y\\ BC\rightarrow &CC, Z&CC, Z&CC, Y\\ CA&CC&CB&CC\\ CB \rightarrow &CC, Z&CC, Z&CC, Y\\ CC&CC&CC&CC\\\ X\rightarrow &Z&Z&Y\\ Y \rightarrow&Z&Z&T\\ Z&Z&Z&Z\\ T\rightarrow&Z&Z&T \end{array} \] Finalement l'automate déterministe est \[ \begin{array}{c|ccc} & a&b&c\\\hline \rightarrow \{AA\}&\{BC\}&\{CB\}&\{CC\}\\ \{BC\}\rightarrow &\{CC, Z\}&\{CC, Z\}&\{CC, Y\}\\ \{CB\}\rightarrow &\{CC, Z\}&\{CC, Z\}&\{CC, Y\}\\ \{CC\}&\{CC\}&\{CC\}&\{CC\}\\ \{CC, Z\}&\{CC, Z\}&\{CC, Z\}&\{CC, Z\}\\ \{CC, Y\}\rightarrow &\{CC, Z\}&\{CC, Z\}&\{CC, T\}\\ \{CC, T\}\rightarrow &\{CC, Z\}&\{CC, Z\}&\{CC, T\} \end{array} \] En renommant les sommets, on arrive à \[ \begin{array}{c|ccc} & a&b&c\\\hline \rightarrow A&B&C&D\\ B\rightarrow &E&E&F\\ C\rightarrow &E&E&F\\ D&D&D&D\\ E&E&E&E\\ F\rightarrow &E&E&G\\ G\rightarrow &E&E&G \end{array} \] \[ \xymatrix@C=2.519cm@R=0.719cm{ &&&&&&\\ &&&B\ar[u]\ar[d]_{a, b}\ar@/^1.19pc/[rrd]^{c}&&&\\ \ar[r]&A\ar@/^1.19pc/[rru]^a\ar@/_1.19pc/[rrd]_b\ar[r]^c&D\ar@(ru, rd)[]^{a, b, c}&E\ar@(lu, ld)[]_{a, b, c}&G\ar[rd]\ar@(l, ld)[]^c\ar[l]_{a, b}&F\ar@/_1.19pc/[ll]_{a, b}\ar[l]_c\ar[r]&\\ &&&C\ar[d]\ar[u]^{a, b}\ar@/_1.19pc/[rru]_{c}&&&\\ &&&&&& } \]

Exercice


Sur l'alphabet \( \Sigma=\{a, b\}\) déterminer des automates reconnaissant les REGEX suivantes.
  1. \( ab^*\)
  2. \( (ab)^*\)
  3. \( a+b^*\)
  4. \( (a+b)^*\)