1997 | OriginalPaper | Chapter
Limitations of Finite Automata
Author : Dexter C. Kozen
Published in: Automata and Computability
Publisher: Springer New York
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
We have studied what finite automata can do; let’s see what they cannot do. The canonical example of a nonregular set (one accepted by no finite automaton) is $$B = \{ {a^n}{b^n}|n0\} = \{ \in ,ab,aabb,aaabbb,aaaabbbb,...\} $$ , the set of all strings of the form a*b* with equally many a’s and b’s.