Teorema de Myhill-Nerode

Acerca da teoria de Linguagens Formais, o Teorema de Myhill-Nerode fornece uma condição necessária e suficiente para que uma linguagem seja regular. O nome do teorema refere-se a John Myhill e Anil Nerode, que o provaram na Universidade de Chicago em 1958 (Nerode 1958).

Enunciado do teorema

Dada uma linguagem L e um par de cadeias x e y, defina uma extensão de distinção como sendo uma cadeia z tal que exatamente uma das duas cadeias xz e yz pertencem a L.

Defina a relação R_L sobre cadeias através da regra de que x R_L y se não há extensão de distinção para x e y. É fácil mostrar que R_L é uma relação de equivalência sobre cadeias, e portanto divide o conjunto de todas as cadeias finitas entre classes de equivalência.

O Teorema de Myhill-Nerode afirma que L é regular se e somente se R_L possui um número finito de classes de equivalência, e ainda que o número de estados no menor autômato finito determinístico (AFD) que reconhece L é igual ao número de classes de equivalência em R_L. Em particular, isso implica que existe um AFD canônico único com número mínimo de estados.

Intui-se então que partindo-se de tal autômato mínimo, quaisquer cadeias x e y que o levem ao mesmo estado estarão na mesma classe de equivalência; e se parte-se de uma partição das classes de equivalência, é possível facilmente construir um autômato que utiliza seu estado para rastrear as classes de equivalência contendo a parte da cadeia vista até o momento.

Prova

Se L é uma linguagem regular, então, por definição, existe um AFD A = (Q, Σ, δ, q, F) , com um número finito de estados, que o reconhece. Se existem n estados, então divida o conjunto de palavras em subconjuntos, onde o subconjunto S_i é o conjunto de palavra tal que, dado S_i como entrada para o AFD A, a entrada para no estado i do autômato. Para toda palavra x e y (x, y ∈ Σ*) que se encontram em um mesmo estado q (q ∈ Q), e para toda escolha de uma terceira palavra z (z ∈ Σ*) um outro estado q_j pertencente ao autômato A (q_j ) que é atingido por xz (palavra x concatenada com a palavra z), também é alcançado por yz (palavra y concatenada com a palavra z), portanto deve-se aceitar tanto xz quanto yz (se q ∈ F), ou rejeitá-los caso contrário (se q ∉ F). Com isso, concluímos que nenhuma palavra z pode ser uma extensão diferencial para x e y, logo, tais palavras (x e y) estão relacionadas com R_L, portanto S_i é um subconjunto de uma classe de equivalência de R_L. Combinando este fato com o fato de que cada membro de uma dessas classes de equivalência pertence a um dos conjuntos S_i, o que dá uma relação muitos (estados de A) para um(a) (classe de equivalência implicando que o número de classes de equivalência é finito e no máximo n ( n = |Q| ).

Na outra direção, suponha que R_L tenha finitas classes de equivalência. Neste caso, é possível construir um autômato finito determinístico que possui um estado para cada classe de equivalência. O estado inicial do autômato corresponde a classe de equivalência contendo palavra vazia (ε), e a função de transição de um estado q_k ao receber um símbolo s, leva o autômato a um novo estado, correspondente a classe de equivalência contendo a palavra xy. A definição da relação de Myhill-Nerode implica que a função de transição é bem-definida: não importa quão representativa seja a palavra x escolhida para o estado q_k, o valor da função de transição será o mesmo. O estado deste autômato é de aceitação se a classe de equivalência correspondente contém uma palavra em L; neste caso, novamente, a definição de relação implica que toda palavra na mesma classe de equivalência deve também pertencer a L, caso contrário à palavra vazia seria uma distinção para alguns pares de palavras nesta classe.

Portanto, a existência de um autômato finito, o qual reconhece L, implica que a relação de Myhill-Nerode possui um número finito de classes de equivalência, no máximo igual ao numero n de estados de um autômato, e a existência de um número finito de classes de equivalência, implica que existe um autômato com n estados.

Uso e consequências

O teorema de Myhill-Nerode pode ser utilizado para mostrar que a linguagem L é regular provando-se que o número de classes de equivalência de R_L é finito. Isso pode ser feito através de uma análise de caso exaustiva na qual, começando da cadeia vazia, extensões de distinção são utilizadas para encontrar classes de equivalência adicionais até que nenhuma outra possa ser encontrada. Por exemplo, a linguagem consistindo de números binários que podem ser divididos por 3 é regular. Dada a cadeia vazia, 00 (ou 11), 01 e 10 são extensões de distinção resultantes nas três classes (correspondendo aos números que resultam em resto 0, 1 e 2 quando divididos por 3), mas após essa etapa não há mais extensõe de distinção. O autômato mínimo que aceita essa linguagem teria três estados correspondendo a essas três classes de equivalência.

Outro corolário imediato do teorema é que se uma linguagem define um conjunto infinito de classes de equivalência, ela não é regular. Este é o corolário frequentemente utilizado para provar que uma linguagem não é regular.

Ver também

• Lema do bombeamento, um método alternativo para provar que uma linguagem não é regular.

Referências

• Henzinger, Tom (2003), Lecture 7: Myhill–Nerode Theorem (PDF), consultado em 12 de julho de 2011, cópia arquivada (PDF) em  🔗 .
• Hopcroft, John E.; Ullman, Jeffrey D. (1979), «Chapter 3», Introduction to Automata Theory, Languages, and Computation, ISBN 0-201-02988-X, Reading, Massachusetts: Addison-Wesley Publishing .
• Nerode, Anil (1958), «Linear Automaton Transformations», Proceedings of the AMS, 9 .
• Regan, Kenneth (2007), Notes on the Myhill-Nerode Theorem (PDF) .