regular languageRegularLanguage2002-02-23 22:20:262009-08-08 23:08:59Definitionregular grammarregular expressionChomsky\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}A \emph{regular grammar} is a context-free grammar where a production has one of the following three forms:
$$A\to \lambda,\qquad A\to u, \qquad A\to vB$$
where $A,B$ are non-terminal symbols, $u,v$ are terminal words, and $\lambda$ the empty word. In BNF, they are:
\begin{eqnarray*}
\verb.<.\textit{non-terminal}\verb.>. & ::= & terminal \\
\verb.<.\textit{non-terminal}\verb.>. & ::= & terminal\,\verb.<.\textit{non-terminal}\verb.>. \\
\verb.<.\textit{non-terminal}\verb.>. & ::= & \lambda
\end{eqnarray*}
A \emph{regular language} (also known as a \emph{regular set} or a \emph{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 $\lbrace a,b,c\rbrace$, the regular language associated with the regular expression $a(b\cup c)^*a$ is the set $$\lbrace a\rbrace \circ \lbrace b,c\rbrace^* \circ \lbrace a\rbrace=\lbrace awa\mid w\mbox{ is a word in two letters }b\mbox{ and }c\rbrace,$$ 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 $\Sigma$. Let $\mathcal{R}(\Sigma)$ be the smallest subset of $P(\Sigma^*)$ (the power set of the set of words over $\Sigma$, in other words, the set of languages over $\Sigma$), among all subsets of $P(\Sigma^*)$ with the following properties:
\begin{itemize}
\item $\mathcal{R}(\Sigma)$ contains all sets of cardinality no more than 1 (i.e., $\varnothing$ and singletons);
\item $\mathcal{R}(\Sigma)$ is closed under set-theoretic union, concatenation, and Kleene star operations.
\end{itemize}
Then $L$ is a regular language over $\Sigma$ iff $L\in \mathcal{R}(\Sigma)$.
\textbf{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$.
\textbf{Remark}. Closure properties on the family of regular languages are: union, intersection, complementation, set difference, concatenation, Kleene star, homomorphism, inverse homomorphism, and reversal.
\begin{thebibliography}{9}
\bibitem{as} A. Salomaa {\em Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25}. Cambridge (1985).
\end{thebibliography}