Regular Language

languages

Definition

Regular Language

A language is called regular if there exists a finite automaton that accepts it.

Equivalently: A language is called regular if all words in the language are formed by and closed under unity, concatenation or star exponent.

Formally, a set ${\mathcal{L}}_{\text{reg}}(\Sigma )$ of regular languages over $\Sigma$ is the smallest set such that:

• $\{\},\{a\}\in {\mathcal{L}}_{\text{reg}}(\Sigma )$ for all $a\in \Sigma$
• $A,B\in {\mathcal{L}}_{\text{reg}}(\Sigma )⟹A\cup B,A\cdot B,A^{\ast }\in {\mathcal{L}}_{\text{text}}(\Sigma )$

Operations

Unity

$$\{a,b,\dots \}\cup \{c,d,\dots \}=\{a,b,\dots ,c,d,\dots \}$$

Concatenation

$$\{a,b,\dots \}\cdot \{c,d,\dots \}=\{ac,ad,\dots ,bc,bd,\dots \}$$

Exponents

$$\begin{array}{rl}{L}^0& =\{\epsilon \}\\ L^1& =L\cdot L^0=L\\ L^n& =L^0\cdot L^1\cdot \dots \cdot L^n\end{array}$$

Star

$$L^{\ast }=\bigcup _{n\ge 0}{L}^n$$

Plus

$$L^{+}=\bigcup _{n\ge 1}{L}^n$$

Closure

The class of regular languages over an alphabet $\Sigma$ is closed under the following operations:

• union, concatenation, and Kleene star by definition,
• plus, since

$$A^{+}=A^{\ast }\cdot A,$$

• complement with respect to ${\Sigma }^{\ast }$,
• intersection, since

$$A\cap B=\overline{\overline{A}\cup \overline{B}},$$

• difference, since

$$A\setminus B=A\cap \overline{B},$$

• reversal, by reversing all transitions and exchanging start and accepting states in a suitable automaton construction,
• homomorphisms, by replacing each symbol $a$ by the word $h(a)$.

Observation

For complement, one first constructs a deterministic finite automaton and then swaps accepting and non-accepting states. The trap state must be included if needed so that the transition function is total.

Limitation

Regularity has limitations. Take the following language:

$$L=\{0^n{1}^n\mid n\ge 0\}$$

The language $L$ above demands that we have the number of ones is equal to the preceding number of zeros, i.e. the machine has to remember the number of zeros. Given that $n$ is not bounded, the machine has to be able to remember an unbounded number of possibilities, which is impossible with a finite number of states (in a finite automaton).

Examples

Finite complement

Every language with finite complement is regular.

Let $L$ be a language such that $\overline{L}$ is finite. Then $\overline{L}$ is regular, because every finite language is regular.

Regular languages are closed under complement. Hence $L$ is regular.