Myhill–Nerode theorem
Teorema de Myhill-Nerode
- Date
- 1957 · confidence high
- Place
- Chicago, Illinois, United States
- Credited to
- John Myhill y Anil Nerode
- Field
- Knowledge & symbols
What was discovered
Formal-language theory theorem giving a necessary and sufficient condition for a language to be regular, proved by John Myhill and Anil Nerode at the University of Chicago.
What it led to
- Methods for minimizing finite automata
- Practical criteria for proving a language is not regular
- Theoretical foundation of automata theory and compilers
- Algorithmic basis for constructing minimal automata