===== I. Machines de Turing =====

==== Introduction ====

  * On s'occupe [dans ce cours?] de langages (formels) : ensembles de mots sur un alphabet \$ \Sigma : \quad L \subset \Sigma^* \$.
  * Nous aurions vu des classes de langages intéressants.

=== Langages Rationnels ===

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__.

=== Langages non-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 q<sub>2</sub> 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 ^
| q<sub>0</sub> | a | e | a | q<sub>1</sub> |
| q<sub>1</sub> | a | e | a | q<sub>1</sub> |
| q<sub>1</sub> | b | a | e | q<sub>2</sub> |
| q<sub>2</sub> | b | a | e | q<sub>2</sub> |

Ceci est un langage __non rationnel__ (Lemme de l'étoile) ((pumping lemma))

FIXME : completer cette partie sur les langages algébriques (hors contexte) à l'aide du livre de Grune sur le parsing.

==== Machines de Turing ====

{{page>c_et_c_def_1&nofooter}}

=== Exemple ===

  * \$ 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

  * lecture d'un ''a'' => efface ''a'' et passer dans un état pré-mouvement à droite
  * faire un déplacement à droite et repasser dans l'état précédent

=== Exercice ===

  * \$ \Sigma=\left\{ a,  b,\sqcup , \triangleright \right\} \$

^  \$ \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) \$ |




{{page>c_et_c_def_2&nofooter}}

=== Exemple ===


{{page>c_et_c_def_3&nofooter}}


=== Calcul (déf.) ===

{{page>c_et_c_def_calc&nofooter}}


=== Exercice ===

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.


=== Exercice ===

Ecrire une MT pour effacer jusqu'au premier blanc, puis revenir au point de départ. \$\Sigma=\left\{ a, \sqcup, \triangleright \right\} \$.