regular language

A regular grammar is a context-free grammar where a production has one of the following three forms:

$$A\to \lambda ,A\to u,A\to vB$$

where $A,B$ are non-terminal symbols, $u,v$ are terminal words, and $\lambda$ the empty word. In BNF, they are:

$::=$$terminal$

$::=$

$::=$$\lambda$

A regular language (also known as a regular set or a regular event) is the set of strings generated by a regular grammar.Regular grammars are also known as Type-3 grammars in the Chomsky hierarchy.

A regular grammar can be represented by a deterministic or non-deterministic finite automaton. Such automata can serve to either generate or accept sentences in a particular regular language. Note that since the set of regular languages is a subset of context-free languages, any deterministic or non-deterministic finite automaton can be simulated by a pushdown automaton.

There is also a close relationship between regular languages and regular expressions. With every regular expression we can associate a regular language. Conversely, every regular language can be obtained from a regular expression. For example, over the alphabet $\{a,b,c\}$, the regular language associated with the regular expression $a{(b\cup c)}^{*}a$ is the set

$$\{a\}\circ {\{b,c\}}^{*}\circ \{a\}=\{awa\mid w\text{ is a word in two letters }b\text{ and }c\},$$

where $\circ$ is the concatenation operation, and $*$ is the Kleene star operation. Note that $w$ could be the empty word $\lambda$.

Yet another way of describing a regular language is as follows: take any alphabet $\mathrm{\Sigma }$. Let $ℛ(\mathrm{\Sigma })$ be the smallest subset of $P({\mathrm{\Sigma }}^{*})$ (the power set of the set of words over $\mathrm{\Sigma }$, in other words, the set of languages over $\mathrm{\Sigma }$), among all subsets of $P({\mathrm{\Sigma }}^{*})$ with the following properties:

• $ℛ(\mathrm{\Sigma })$ contains all sets of cardinality no more than 1 (i.e., $\mathrm{\varnothing }$ and singletons);

• $ℛ(\mathrm{\Sigma })$ is closed under set-theoretic union, concatenation, and Kleene star operations.

Then $L$ is a regular language over $\mathrm{\Sigma }$ iff $L\in ℛ(\mathrm{\Sigma })$.

Normal form. Every regular language can be generated by a grammar whose productions are either of the form $A\to aB$ or of the form $A\to \lambda$, where $A,B$ are non-terminal symbols, and $a$ is a terminal symbol. Furthermore, for every pair $(A,a)$, there is exactly one production of the form $A\to aB$.

Remark. Closure properties on the family of regular languages are: union, intersection, complementation, set difference, concatenation, Kleene star, homomorphism, inverse homomorphism, and reversal.