TD 2 - Machines de Turing

exercice 1. Déplacements sur le ruban

question 1. Avancer jusqu’à un symbole

Solution :

question 2. Remplacer

Solution :

exercice 2. Copies et effacements

question 1. Effacer

Solution :

question 2. Effacer jusqu’à un symbole

Solution :

question 3. Insérer

Solutions :

• Insérer avant :
• Insérer après :
• Insérer et se replacer :

question 4. Copier

Solution :

exercice 3. Machine mystère

Voir machine :

exercice 4. Langages réguliers

question 1. Contient aab, finit par b

Solutions :

• non-déterministe :
• déterministe :

question 2. \( \tt a^\star ba^\star b\)

Solution :

question 3. Contient abc mais pas bb

Solutions :

• traduction d'un automate :
• algo non réalisable avec un automate :

exercice 5. Langages hors-contextes

question 1. Parenthèses

Solution :

question 2. \( {\tt a}^n {\tt b}^n \)

Solution :

exercice 6. Séquences exponentielles

Solution :

exercice 7.

question 1. Carrés séparés d’un X

Solution :

question 2. Insérer X au milieu

Solution :

question 3. Détecter les carrés

Solution :

exercice 8. Calculs unaires

question 1. Calculer 0 en unaire

Solution :

question 2. Incrémenter en unaire

Solution :

question 3. Calculer l’addition en unaire

Solution :

exercice 9. Calculs binaires

question 1. Calculer 0 en binaire

Solution :

question 2. Incrémenter en binaire

Solution :

question 3. Calculer l’addition en binaire

Solution :