A corresponde à função de transição que recebe um estado ou um símbolo de entrada que sempre retorna um conjunto de estados como resultado.  B tem a capacidade de adivinhar algo sobre sua entrada ao testar valores. C pode, para cada entrada, transitar a partir do seu estado atual em um e somente um estado.  D permite zero, uma ou n transições para os estados de entrada. E consegue estar em vários estados ao mesmo tempo.

A a*b(cb)a*. B aba(cb). C a*b(cb)*a. D a*b*c*b*a*.