Contrôle continu sur table (2022)

exercice 1

Écrire une machine de Turing qui reconnaît le langage suivant sur l’alphabet \(\Sigma = \left\{a, b\right\}\) :

\[L_1 := \left[ ab^\star (aa)^\star\right].\]

Solution : avec 1 ruban

exercice 2

Écrire une machine de Turing qui reconnaît le langage suivant sur l’alphabet \(\Sigma = \left\{a, b\right\}\) :

\[L_2 := \left\{w ~\middle|~ \left|w \right|_a > \left|w \right|_b\right\}.\]

Solutions :

• avec 1 ruban
• avec 2 rubans
• avec 3 rubans

exercice 3

Écrire une machine de Turing qui reconnaît le langage suivant sur l’alphabet\(\Sigma = \left\{a, b, c\right\}\) :

\[L_3 := \left\{w ~\middle|~ \left|w \right|_a = \left|w \right|_b= \left|w \right|_c\right\}.\]

Solutions :

• avec 1 ruban
• avec 4 rubans