Myhill–Nerode theorem

Myhill–Nerode theorem This article needs additional citations for verification. Ajude a melhorar este artigo adicionando citações a fontes confiáveis. O material sem fonte pode ser contestado e removido. Encontrar fontes: "Myhill–Nerode theorem" – notícias · jornais · livros · acadêmico · JSTOR (Setembro 2020) (Saiba como e quando remover esta mensagem de modelo) In the theory of formal languages, the Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1958 (Nerode 1958).

Conteúdo 1 Declaração 2 Prova 3 Use and consequences 4 Generalizações 5 Veja também 6 Referências 7 Further reading Statement Given a language {estilo de exibição L} , and a pair of strings {estilo de exibição x} e {estilo de exibição y} , define a distinguishing extension to be a string {estilo de exibição com} such that exactly one of the two strings {displaystyle xz} e {displaystyle yz} belongs to {estilo de exibição L} . Define a relation {estilo de exibição {}_{eu}{sim }} on strings as {estilo de exibição x;{}_{eu}{sim } y} iff there is no distinguishing extension for {estilo de exibição x} e {estilo de exibição y} . It is easy to show that {estilo de exibição {}_{eu}{sim }} is an equivalence relation on strings, and thus it divides the set of all strings into equivalence classes.

The Myhill–Nerode theorem states that a language {estilo de exibição L} is regular if and only if {estilo de exibição {}_{eu}{sim }} has a finite number of equivalence classes, and moreover, that this number is equal to the number of states in the minimal deterministic finite automaton (DFA) recognizing {estilo de exibição L} . Em particular, this implies that there is a unique minimal DFA for each regular language (Hopcroft & Ullman 1979).

Some authors refer to the {estilo de exibição {}_{eu}{sim }} relation as Nerode congruence,[1][2] in honor of Anil Nerode.

Proof If {estilo de exibição L} is a regular language, then by definition there is a DFA {estilo de exibição A} that recognizes it, with only finitely many states. If there are {estilo de exibição m} states, then partition the set of all finite strings into {estilo de exibição m} subsets, where subset {estilo de exibição S_{eu}} is the set of strings that, when given as input to automaton {estilo de exibição A} , cause it to end in state {estilo de exibição eu} . For every two strings {estilo de exibição x} e {estilo de exibição y} that belong to the same subset, and for every choice of a third string {estilo de exibição com} , automaton {estilo de exibição A} reaches the same state on input {displaystyle xz} as it reaches on input {displaystyle yz} , and therefore must either accept both of the inputs {displaystyle xz} e {displaystyle yz} or reject both of them. Portanto, no string {estilo de exibição com} can be a distinguishing extension for {estilo de exibição x} e {estilo de exibição y} , so they must be related by {estilo de exibição {}_{eu}{sim }} . Desta forma, {estilo de exibição S_{eu}} is a subset of an equivalence class of {estilo de exibição {}_{eu}{sim }} . Combining this fact with the fact that every member of one of these equivalence classes belongs to one of the sets {estilo de exibição S_{eu}} , this gives a many-to-one relation from states of {estilo de exibição A} to equivalence classes, implying that the number of equivalence classes is finite and at most {estilo de exibição m} .

In the other direction, Suponha que {estilo de exibição {}_{eu}{sim }} has finitely many equivalence classes. Nesse caso, it is possible to design a deterministic finite automaton that has one state for each equivalence class. The start state of the automaton corresponds to the equivalence class containing the empty string, and the transition function from a state {estilo de exibição X} on input symbol {estilo de exibição y} takes the automaton to a new state, the state corresponding to the equivalence class containing string {displaystyle xy} , Onde {estilo de exibição x} is an arbitrarily chosen string in the equivalence class for {estilo de exibição X} . The definition of the Myhill–Nerode relation implies that the transition function is well-defined: no matter which representative string {estilo de exibição x} is chosen for state {estilo de exibição X} , the same transition function value will result. A state of this automaton is accepting if the corresponding equivalence class contains a string in {estilo de exibição L} ; nesse caso, novamente, the definition of the relation implies that all strings in the same equivalence class must also belong to {estilo de exibição L} , for otherwise the empty string would be a distinguishing string for some pairs of strings in the class.

Desta forma, the existence of a finite automaton recognizing {estilo de exibição L} implies that the Myhill–Nerode relation has a finite number of equivalence classes, at most equal to the number of states of the automaton, and the existence of a finite number of equivalence classes implies the existence of an automaton with that many states.

Use and consequences The Myhill–Nerode theorem may be used to show that a language {estilo de exibição L} is regular by proving that the number of equivalence classes of {estilo de exibição {}_{eu}{sim }} é finito. This may be done by an exhaustive case analysis in which, beginning from the empty string, distinguishing extensions are used to find additional equivalence classes until no more can be found. Por exemplo, the language consisting of binary representations of numbers that can be divided by 3 is regular. Given the empty string, {estilo de exibição 00} (ou {estilo de exibição 11} ), {estilo de exibição 01} e {estilo de exibição 10} are distinguishing extensions resulting in the three classes (corresponding to numbers that give remainders 0, 1 e 2 when divided by 3), but after this step there is no distinguishing extension anymore. The minimal automaton accepting our language would have three states corresponding to these three equivalence classes.

Another immediate corollary of the theorem is that if for a language {estilo de exibição L} the relation {estilo de exibição {}_{eu}{sim }} has infinitely many equivalence classes, it is not regular. It is this corollary that is frequently used to prove that a language is not regular.

Generalizations The Myhill–Nerode theorem can be generalized to tree automata.

See also Pumping lemma for regular languages, an alternative method for proving that a language is not regular. The pumping lemma may not always be able to prove that a language is not regular. Syntactic monoid References ^ Brzozowski, Janusz; Szykuła, Marek; Ye, Yuli (2018), "Syntactic Complexity of Regular Ideals", Theory of Computing Systems, 62 (5): 1175–1202, doi:10.1007/s00224-017-9803-8, HDL:10012/12499, S2CID 2238325 ^ Crochemore, Maxime; et al. (2009), "From Nerode's congruence to suffix automata with mismatches", Theoretical Computer Science, 410 (37): 3471–3480, doi:10.1016/j.tcs.2009.03.011 Hopcroft, John E.; Ullman, Jeffrey D. (1979), "Capítulo 3", Introduction to Automata Theory, Languages, and Computation, Leitura, Massachusetts: Addison-Wesley Publishing, ISBN 0-201-02988-X. Nerode, Anil (1958), "Linear Automaton Transformations", Proceedings of the AMS, 9 (4): 541–544, doi:10.1090/S0002-9939-1958-0135681-9, JSTOR 2033204. Regan, Kenneth (2007), Notes on the Myhill-Nerode Theorem (PDF), recuperado 2016-03-22. Further reading Bakhadyr Khoussainov; Anil Nerode (6 dezembro 2012). Automata Theory and its Applications. Springer Science & Business Media. ISBN 978-1-4612-0171-7. Categorias: Formal languagesTheorems in discrete mathematicsFinite automata