Regular Language

In computing theory, a regular language is one that is accepted by a finite automaton.

Equivalent Characterizations

• $A$ is a regular language.
• $A$ is accepted by a deterministic finite automaton(DFA).
• $A$ is accepted by an alternating finite automaton(AFA).
• $A$ is accepted by a non-deterministic finite automaton(NFA).
• $A$ is accepted by a generalized non-deterministic finite automaton(GNFA).
• $A$ can be described by a regular expression(RE).

Closure Properties

Suppose $A,B\subseteq \Sigma ^{*}$ are regular languages. Then the following languages are also regular.

• $A\cup B=\{x~|~x\in A\ \mathrm {or} \ x\in B\}$ (union)
• $A\cap B=\{x~|~x\in A\ \mathrm {and} \ x\in B\}$ (intersection)
• ${\bar {A}}=\{x\in \Sigma ^{*}~|~x\not \in A\}$ (complement)
• $AB=\{xy~|~x\in A\ \mathrm {and} \ y\in B\}$ (concatenation)
• $A^{*}=\{x_{1}x_{2}\ldots x_{n}~|~n\geq 0\ \mathrm {and} \ x_{i}\in A,~1\leq i\leq n\}$ (asterate)
• $A-B=\{x-y~|~x\in A\ \mathrm {and} \ y\in B\}$ (difference)
• $A^{R}=\{x^{R}|~x\in A\ \}$ (reversal)

Regular languages are also closed under homomorphic images and preimages. Suppose $C\subseteq \Gamma ^{*}$ is a regular language and $h:\Sigma ^{*}\to \Gamma ^{*}$ is a string homomorphism. Then the following languages are regular.

• $h(A)=\{h(x)~|~x\in A\}\subseteq \Gamma ^{*}$ (homomorphic image)
• $h^{-1}(C)=\{x~|~h(x)\in C\}\subseteq \Sigma ^{*}$ (homomorphic preimage)