A formal language L is regular if it is accepted by some finite automaton.
Alternatively, a regular language is a language that can be defined by a regular expression (in the strict formal sense as opposed to many modern regular expression engines which augment with non-regular features). The equivalence of regular expressions and finite automata is known as Kleene’s theorem.
Limitation
Intuitively, since a DFA has only finitely many states, it cannot “remember” arbitrary amounts of information such as counting or matching structure. For example, below are two canonical examples of non-regular languages:
- Strings consisting of arbitrary number of
s followed by an equal number of s
- Strings of balanced parentheses
- E.g.
(),()(),(())