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.

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$$

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).