Représentation graphique d'un automate fini déterministe M_a
\Sigma = \left\{ a,b,c \right\}
\Sigma^* = \left\{ e, a, b, c, aa, ab, \ldots \right\}
L\left(M_a\right) = \left\{ a^n | n\in \mathbb{N} \right\} = a^*
On représente la machine par \left(K,\Sigma ,\delta, q_0, \left\{ q_0 \right\} \right) pour la machine de cet exemple, où
q_0 est l'état initial (et final),
K=\left\{ q_0, q_1 \right\} est l'ensemble des états
\delta\left(q_0,a\right)=q_0, \delta\left(q_0, b\right)=\delta\left(q_0, c\right)=q_1, \delta\left( q_1, \forall \sigma \right)=q_1 est la fonction de transition.
Ces automates permettent de décider la classe des langages rationnels.
Automate à pile M_p : \left(\;K,\Sigma, \Gamma, \Delta, q_0, F\right) où
\Gamma est l'ensemble des caractères de contrôle, q_0 et F sont l'état initial et l'état final respectivement.
Les règles de \Delta sont de la forme (lettre lu, lettre dépile)/lettre empilé, nouvelle état.
L \left( M_p\right) = \left\{ a^n b^n \;|\; n\in \mathbb{N} \right\} : j'ai un doute, car je ne vois pas comment cet automate vérifie que le nombre de a égale le nombre de b, seulement que le mot commence par un ou plusieurs a qui sont suivi par un ou plusieurs b. Il faudrait qu'elle sorte de q2 en cas de lecture d'autre qu'un b ou si elle vide la pile avant lecture du dernier b.
| Etat | lu | dépilé | empilé | nouv. état |
| q0 | a | e | a | q1 |
| q1 | a | e | a | q1 |
| q1 | b | a | e | q2 |
| q2 | b | a | e | q2 |
Ceci est un langage non rationnel (Lemme de l'étoile) 1)
: completer cette partie sur les langages algébriques (hors contexte) à l'aide du livre de Grune sur le parsing.
Une machine de Turing (MT) est un quintuplet M=\left(K,\Sigma,\delta,s,H\right) où
K est un ensemble fini d'états
\Sigma est un alphabet (fini) contenant les symboles \sqcup (blanc) et \triangleright (début de mot)
s\in K : état initial
H\in K : ensemble des état d'arrêt
\delta : fonction de transition
\delta: \left(K \setminus H\right) \times \Sigma \mapsto K\times \left(\Sigma \cup \left\{ \leftarrow, \rightarrow\right\}\setminus \left\{ \triangleright \right\}\right)
\left[\delta\left(p,\triangleright\right)=\left(q,\sigma\right)\right]\Rightarrow\left[\sigma=\rightarrow\right]
K=\left\{s, q, h \right\}
\Sigma=\left\{ a, \sqcup , \triangleright \right\}
| \delta = |
| | \sigma |
| état | a | \sqcup | \triangleright |
| s | \left( q,\sqcup \right) | \left( h,\sqcup \right) | \left( s,\rightarrow \right) |
| q | \left( s,a \right) | \left( s,\rightarrow \right) | \left( q,\rightarrow\right) |
Contrairement à la convention utilisée par Minsky, ici nous décomposons lecture/écriture et mouvement en deux temps. Au lieu de effacer l'emplacement courant et se déplacer, par exemple, on fait
| \delta = |
| | \sigma |
| état | a | b | \sqcup | \triangleright |
| s | \left( q,\sqcup \right) | \left( s,\rightarrow \right) | \left( h,\sqcup \right) | \left( s,\rightarrow \right) |
| q | \left( s,a \right) | \left(s,h\right) | \left( s,\rightarrow \right) | \left( q,\rightarrow\right) |
Soit M=\left(K, \Sigma, \delta, s, H\right) une machine de Turing. Une configuration de M est un élément de
K \times \triangleright\Sigma^* \times\left(\Sigma^* \left(\Sigma\setminus \left\{ \sqcup \right\}\right) \cup\left\{ e \right\} \right)
Soientt M=\left(K, \Sigma, \delta, s, H\right) une machine de Turing et \left(q_1,w_1 a_1 u_1\right) et \left(q_2,w_2 a_2 u_2\right) deux configuration de M. On dis qu'on passe de la première à la deuxième en un pas de calcul si et seulement si \exists \beta | \beta\in\left(\Sigma \cup \left\{\leftarrow,\rightarrow\right\}\right) tel que
\delta\left(q_1,a_1\right) = \left(q_2,b\right)
la situation est l'une de ces trois:
b\in\Sigma, \&\quad a_2=b, w_2=w_1, u_2=u_1
b \; =\; \rightarrow, \text{ et } w_2=w_1 a_1 et
b\;=\;\leftarrow, \text{ et } w_1=w_2 a_2 et
On note alors \displaystyle \left(q_1, w_1 a_1 u_1\right) \vdash_{M} \left(q_2, w_2 a_2 u_2\right)
| Cas | w1 | a1 | u1 |
| 2.1 | w2 | a2 | u2 |
| Cas | w1 | a1 | u2=e |
| 2.2 | w2 | a_2=\sqcup | u2=e |
| Cas | w1 | a1 | u1 |
| 3.1 | w2 | a2 | u2 |
Pour toute machine de Turing M,
on note \displaystyle \vdash_{M}^{*} la fermeture réflexive transitive de \vdash_M .
On dit que la configuration C_1 produit la configuration C_2 si et seulement si \displaystyle C_1 \vdash_{M}^{*} C_2
Un calcul de
C_2 à partir de
C_1 est une suite de configurations
C_1 = C^{\left(0\right)} \vdash_M C^{\left(1\right)} \vdash_M C^{\left(2\right)} \vdash_M \cdots \vdash_M C^{\left(n\right)}= C_2
On dit alors qu'on a un calcul de longueur n, et on note
C_1 \vdash_{M}^{\left(n\right)} C_2
Y a-t-il moyen de mieux poser les super et sub params sur les dérives? En notons au passage que \vdash est \vdash.
Ecrire une machine de Turing qui cherche vers la droite une 2ième occurrence de la lettre lu au départ, mais qui s'arrête si elle rencontre deux blancs consécutifs avant cette 2ième occurrence.
Ecrire une MT pour effacer jusqu'au premier blanc, puis revenir au point de départ. \Sigma=\left\{ a, \sqcup, \triangleright \right\} .
