Considere a maquina de Turing a seguir:
Agora considere as seguintes palavras:
- aaaaaaaabb;
- aaaabbbbaaaa;
- aaabbb.

a - aceita, aceita, rejeita.
b - aceita, rejeita, aceita.
c - rejeita, rejeita, aceita.
d - aceita, aceita, aceita.
e - rejeita, rejeita, rejeita.