Eu estou fazendo com máquinas de Turing, às vezes definindo formalmente a função de transição, e às vezes simplesmente descrevendo o algoritmo em alto nível como faz o Sipser.
Pelo que o Coelho disse em aula, eu imagino que qualquer uma das soluções (descrevendo a função de transição, pseudo-código em alto nível ou pseudo-código em baixo nível) deve servir, se a argumentação sobre o consumo de tempo convencer. ;)
Fórum