Um autômato Xor não determinístico (NXA) é sintaticamente um NFA, mas uma palavra é aceita pelo NXA se ele tiver um número ímpar de caminhos de aceitação (em vez de pelo menos um caminho de aceitação no caso de NFA). É fácil ver que, para um idioma regular finito , existe um NFA mínimo que não...
Autômatos residuais de estado finito (RFSAs, definidos em [DLT02]) são NFAs que possuem alguns recursos interessantes em comum com os DFAs. Em particular, sempre existe um RFSA de tamanho mínimo canônico para cada idioma regular, e o idioma reconhecido por cada estado no RFSA é um resíduo, assim...
O algoritmo de Brzozowski para converter um DFA em um DFA equivalente de estado mínimo é extraordinariamente simples: se denota o NFA formado pela reversão de todas as arestas em um DFA , tornando o antigo estado inicial um estado de aceitação, e fazendo o antigo aceitar estados iniciam estados e...