Devoir maison (2022)
Présentation du devoir
Consignes générales
Ce devoir doit être réalisé individuellement. Chaque question vous demande de construire une machine de Turing. On utilisera le simulateur en ligne disponible ici, ou bien celui-ci turingmachinesimulator. Vos réponses devront être interprétable par ces simulateurs : en cas d’erreur de compilation votre réponse ne sera pas corrigée. Toutes les machines à construire opèreront donc sur un ou plusieurs rubans bi-infinis, seront déterministes, et commenceront avec leur entrée sur le premier ruban, et la tête de lecture sur le symbole le plus à gauche de l’entrée.
Structure du rendu
Vos réponses devront être présentées sous forme de fichers texte, interprétable par le simulateur.
Vous rassemblerez les fichiers correspondant à vos réponses à chaque question dans une archive (.zip ou .tar.gz), nommée nom.prenom.dm-cc, qui devra me parvenir par email à l’adresse suivante :
prenom[point]nom[at]u[tiret]pec[point]fr.
Conseils
Il est recommandé d’utiliser des machines à plusieurs rubans pour certaines questions. Comme on va combiner les différentes machines que l’on construit, il est judicieux de choisir des noms d’états différents pour chaque machine. Pensez bien à tester vos réponses sur plusieurs mots d’entrée!
Objectif
On veut construire une machine de Turing qui interprète des expressions arithmétiques en unaire vers des entiers binaires.
Plus précisément, on veut une machine qui, sur une chaîne de caractères en entrée \((1111+(11*111))\), qui encode le calcul \((4+(2\times 3))\), produit la chaîne de caractères 1010, c’est à dire le code binaire de l’entier 10.
On va pour cela procéder en plusieurs étapes:
- Implémenter l’addition et la multiplication d’entiers en unaire.
- Implémenter la conversion d’entiers de unaire à binaire.
- Construire un parseur, qui met une expression arithmétique infixe sous forme suffixe, aussi appelée notation polonaise inverse.
- Assembler ces éléments pour obtenir l’interpréteur souhaité.
Il est recommandé de se documenter sur la notation polonaise inverse, par exemple sur wikipedia.
Exercice 1 : Opérations arithmétiques
Question 1
Construire une machine add telle que:
- L’alphabet d’entrée d’add est \(\left\{ 0,1 \right\}\).
- Sur une entrée \(w=1^n01^m\), la machine accepte, et s’arrète avec:
- le ruban contenant la sortie \(1^{n+m}\);
- si le ruban est non-vide (\(n+m\neq 0\)), la tête de lecture sur la première case non-vide à partir de la gauche.
- La machine rejette les mots mal formattés.
Question 2
En utilisant la machine précédente, construire mult telle que:
- L’alphabet d’entrée de mult est \(\left\{0,1\right\}\).
- Sur une entrée \(w=1^n01^m\), la machine accepte, et s’arrète avec:
- le ruban contenant la sortie \(1^{n\times m}\);
- la tête de lecture sur la première case non-vide (si le ruban est non-vide).
- La machine rejette les mots mal formattés.
Exercice 2 : Conversion unaire vers binaire
\(\newcommand\Nat{\mathbb{N}}\newcommand\code[1]{\left[{#1}\right]_{code}}\) Pour un entier \(n\in\Nat\), on note \(\code{n}\) sa représentation binaire, avec le bit de poids fort à gauche. Les codes des 6 premiers entiers sont donc:
| entier | code |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |
| 3 | 11 |
| 4 | 100 |
| 5 | 101 |
Question 1
Construire une machine incr telle que:
- L’alphabet d’entrée d’incr est \(\left\{0,1\right\}\).
- Sur une entrée \(w=\code{n}\), la machine accepte, et s’arrète avec: le ruban contenant la sortie \(\code{n+1}\) et la tête de lecture sur la première case non-vide.
- La machine rejette les mots mal formattés, c’est à dire qu’elle s’arrète sur un état non-final pour tous les mots du langage :
Question 2
En utilisant la question précédente, implémenter une machine réalisant la conversion unaire binaire, c’est à dire une machine conv qui sur l’entrée 11111 produit la sortie 101.
Exercice 3 : Parseur
Une expression arithmétique peut se représenter de manière arborescente. Par exemple, l’expression \(4+(2\times 3)\) peut se représenter comme le résultat de l’opération \(+\) appliquée à 4 et au résultat d’une seconde opération \(\times\) appliquée à 2 et à 3. \(4\) et \(\times (2,3)\) sont dits opérandes de l’expression qui a \(+\) comme opérateur. Selon ce principe, une autre notation pour cette expression arithmétique est \(+(4,\times(2,3))\), aussi appelée notation polonaise et notamment utilisée sur les calculatrice HP.
Il est à noter qu’il devient ainsi possible de se passer tout à fait de parenthèses : il n’y a aucune ambiguïté lorsqu’on utilise la notation \(+\,4\,\times\,2\,3\).
La notation qui nous intéresse ici est la notation polonaise inverse: pour chaque opération \(n+m\), on écrit \(n\,m\,+\). L’expression \(4+(2\times 3)\) devient donc \(4\,2\,3\,\times\,+\).
Dans notre cas, on va vouloir prendre en entrée des chaînes de caractères sur l’alphabet \(\left\{1,+,*,(,)\right\}\) où:
- \(1\) sert à représenter les entiers en unaire;
- \(+\) et \(*\) sont utilisé pour représenter de manière infixe les opérations arithmétiques d’addition et de multiplication;
- les parenthèses doivent être utilisées à chaque application d’opération.
Plus précisément, une entrée bien formattée doit être conforme à la grammaire ci-dessous:
\[S~\to~ 1^n\,|\,(S+S)\,|\,(S*S)\]Par exemple \((1111+(11* 111))\) est bien formattée, tout comme \(1111\). En revanche \(1(11)\) ne l’est pas, pas plus que \((1+11*1111)\), \(11+1\), ou \((1+11+111)\).
Question 1
Construire une machine qui décide le langage des expressions bien formattées.
Question 2
On veut traduire ces expressions en notation polonaise inverse (NPI). Ceci implique d’effacer les parenthèses, de déplacer les symboles \(+\) et \(*\), et d’insérer des séparateurs (on va utiliser \(0\)) entre les arguments. Ainsi, l’expression \((1111+(11* 111))\) deviendra \(11110110111*+\) On pourra utiliser le pseudo-algorithme suivant, qui utilise une pile (last in first out) d’opérateurs:
- On lit l’entrée, en effaçant les parenthèses ouvrantes, et en recopiant les entiers.
- Lorsequ’on lit un opérateur \(+\) où \(*\), on le remplace par \(0\) et on l’ajoute à la pile.
- Lorsequ’on lit une parenthèse fermante, on retire un opérateur du sommet de la pile, et on l’écrit à la place de cette parenthèse.
En utilisant l’algorithme ci-dessus, construire une machine qui rejette les expressions mal formattées, et convertit les autres en NPI.
Exercice 4 : Interpréteur
Une fois l’expression en NPI, l’interpréter (i.e. calculer le résultat) est aisé1. L’algorithme maintient une pile de nombres:
- Lorsequ’on lit un nombre, on l’ajoute à la pile.
- Lorsequ’on lit un opérateur, on retire les deux premiers nombres de la pile, on leur applique l’opération, et on place le résultat au sommet de la pile.
Après avoir fini de lire l’entrée, on doit avoir un seul nombre dans la pile : le résultat.
Question 1
En utilisant les machines de l’exercice 1 et l’algorithme ci-dessus, constuire une machine qui interprète les expressions en NPI.
Par exemple, sur l’entrée 11110110111*+ on attend en sortie 1111111111.
Question 2
En combinant les différentes machines réalisées jusque là, construire une machine qui prend en entrée des expressions arithmétiques avec:
- les entiers en unaire;
- les opérateurs en notation infixe.
Cette machine doit évaluer l’expression, et convertir le résultat en binaire.
Autrement dit elle doit sur notre exemple (1111+(11*111)), qui code l’expression \(4+(2\times 3)\), produire en sortie le mot 1010, codage binaire de l’entier \(10\).