turing machine

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

Algorithm Analysis

ID Projek: #27988541

Tentang projek