The Myhill-Nerode Theorem provides a necessary and sufficient condition for a formal language to be regular, characterizing regularity in terms of the number of equivalence classes formed by an equivalence relation defined on strings by their future behavior with respect to the language. Named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1957, it is a foundational result of automata theory used both to prove that particular languages are regular and, via the same equivalence classes, to construct the smallest possible deterministic finite automaton recognizing a given regular language.
Facts
StatementA language L is regular if and only if its Myhill-Nerode relation has a finite number of equivalence classes, and this number equals the number of states in the minimal deterministic finite automaton accepting L. 1 Classification
Statement Form Statement FormCharacterization Theorem 1 Connections
Has Statement Form
In Branch
Principal Result Of
Source Anil Nerode (Wikipedia)
Source John Myhill (Wikipedia)
Proved By
Source Myhill-Nerode theorem (Wikipedia)
Source Myhill-Nerode theorem (Wikipedia)
Sources
1. Myhill-Nerode theorem (Wikipedia)
Statement
that this number is equal to the number of states in the minimal deterministic finite automaton (DFA) accepting L.
History
proved it at the University of Chicago in 1957
Proved By: John Myhill, Lead sentence
The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1957..
Proved By: Anil Nerode, Lead sentence
The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1957..
In Group: Computability and Complexity Theory, Lead section
In the theory of formal languages, the Myhill-Nerode theorem provides a necessary
View the SourceAnil Nerode (Wikipedia)
Principal Result Of: Anil Nerode, Career, Myhill-Nerode theoremQuote, Principal Result Of: Anil Nerode, Career, Myhill-Nerode theorem
With John Myhill, Nerode proved the Myhill-Nerode theorem
John Myhill (Wikipedia)
Principal Result Of: John Myhill, Contributions, formal languagesQuote, Principal Result Of: John Myhill, Contributions, formal languages
In the theory of formal languages, the Myhill-Nerode theorem, proven by Myhill and Anil Nerode, characterizes the regular languages as the languages that have only finitely many inequivalent prefixes.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.