Editing Regular language (section)

== Examples ==
All finite languages are regular; in particular the [[empty string]] language {{nowrap|1={{mset|ε}} = ∅*}} is regular. Other typical examples include the language consisting of all strings over the alphabet {{mset|''a'', ''b''}} which contain an even number of ''a''s, or the language consisting of all strings of the form: several ''a''s followed by several ''b''s.

A simple example of a language that is not regular is the set of strings {{mset|''a''<sup>''n''</sup>''b''<sup>''n''</sup> | ''n'' ≥ 0}}.<ref>Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).</ref> Intuitively, it cannot be recognized with a finite automaton, since a finite automaton has finite memory and it cannot remember the exact number of a's. Techniques to prove this fact rigorously are given [[#Location in the Chomsky hierarchy|below]].