turing machine
€8-30 EUR
Paiement à la livraison
Le problème à traiter est celui du drapeau tricolore, sur une machine de Turing.
Données :
• un mot de la forme XXX ... XXX (X ^n) de longueur n (n > 0).
Résultat :
• le mot LLL…LLLMMM…MMMNNN…NNN (L ^ (i) M ^ (j) N ^ (k)), avec i≤j≤k≤i+1 avec n=i+j+k.
Exemples :
• XXXXXX donne LLMMNN
• XXXXXXXX donne LLMMMNNN
1. Donner un premier algorithme simple pour le problème sur une machine à une bande (il peut
être en O(n2)). Le but de cette partie est la prise en main du simulateur.
2. Donner une machine (toujours sur une seule bande) pour ce même problème, mais avec le moins
d’états possibles.
3. Donner ensuite un algorithme efficace pour le même problème (en temps O(nlogn)) (toujours
sur une seule bande)
4. Donner une machine de complexité linéaire en utilisant une machine à deux bandes
Nº du projet : #27988541