Définition
Soient \( \A\) et \( \mathscr{B}\) des automates sur un langage \( \Sigma\) . On définit \( \A+\mathscr{B}\) comme l'automate avec les règles suivantes.
- Alphabet.
- \( \Sigma_{\A+\mathscr{B}} = \Sigma\)
- États.
- \( E_{\A+\mathscr{B}} = E_\A\times E_{\mathscr{B}}\)
- État initial.
- \( I_{\A+\mathscr{B}}=I_\A\times I_\mathscr{B}\)
- États finaux.
- \( F_{\A+\mathscr{B}}=\left(F_\A\times E_\mathscr{B}\right)\cup\left(E_\A\times F_\mathscr{B}\right)\)
- Transitions.
- \( \forall (A, B)\in E_{\A+\mathscr{B}}\) , \( \forall x\in \Sigma\) , \( \tau_{\A+\mathscr{B}}((A, B), x) = \left(\tau_\A(A, x), \tau_\mathscr{B}(B, x)\right)\) .
Exercice
Donner la représentation sagittale de l'automate \( \A+\mathscr{B}\) sur \( \Sigma=\{a, b\}\) où
L'automate \( \A\) est
\[\xymatrix{
\ar[r]&A\ar@(lu, ru)[]^b\ar[r]^a&B\ar@(lu, ru)[]^b\ar[r]^a&C\ar@/^1pc/[ll]^a\ar@(lu, ru)[]^b\ar[r]&\\
}\]
L'automate \( \mathscr{B}\) est
\[\xymatrix{
\ar[r]&A\ar@(lu, ru)[]^a\ar@/^0.519pc/[r]^b&B\ar@(lu, ru)[]^a\ar@/^0.519pc/[l]^b\ar[r]&
}\]
Proposition
Soient \( \A\) et \( \mathscr{B}\) des automates sur un langage \( \Sigma\) .
\[L(\A+\mathscr{B})=L(\A)\cup L(\mathscr{B})\]
Démonstration
C'est une conséquence triviale de la définition.
Exercice
Soit \( \Sigma=\{a, b\}\) .
- Donner un automate reconnaissant les langages \( \{a\}\) et \( \{b\}\) .
- Donner un automate qui reconnait le langage \( \Sigma\) . Donnez une REGEX reconnaissant ce langage.