1997 | OriginalPaper | Buchkapitel
Regular Languages
verfasst von : Sheng Yu
Erschienen in: Handbook of Formal Languages
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Regular languages and finite automata are among the oldest topics in formal language theory. The formal study of regular languages and finite automata can be traced back to the early forties, when finite state machines were used to model neuron nets by McCulloch and Pitts [83]. Since then, regular languages have been extensively studied. Results of early investigations are, for example, Kleene’s theorem establishing the equivalence of regular expressions and finite automata [69], the introduction of automata with output by Mealy [86] and Moore [88], the introduction of nondeterministic finite automata by Rabin and Scott [99], and the characterization of regular languages by congruences of finite index by Myhill [90] and Nerode [91].