1997 | OriginalPaper | Chapter
Regular Languages
Author : Sheng Yu
Published in: Handbook of Formal Languages
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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].