Macchine di Turing deterministiche a nastro singolo

Puoi trovare numerosi esempi di diagrammi degli stati di macchine di Turing sul sito turingmachine.io.

Esercizio 01

Disegna il diagramma degli stati di una DTM che riconosce solo sequenze sull’alfabeto {a, b} della forma: aⁿbⁿ, dove n è un numero naturale positivo.

Esercizio 02

Disegna il diagramma degli stati di una DTM che riconosce solo sequenze sull’alfabeto {a, b, c} della forma: aⁿbⁿcⁿ, dove n è un numero naturale positivo.