You are here
Homeregular language
Primary tabs
regular language
A regular grammar is a contextfree 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 nonterminal symbols, $u,v$ are terminal words, and $\lambda$ the empty word. In BNF, they are:
$\displaystyle\verb.<.\textit{nonterminal}\verb.>.$  $\displaystyle::=$  $\displaystyle terminal$  
$\displaystyle\verb.<.\textit{nonterminal}\verb.>.$  $\displaystyle::=$  $\displaystyle terminal\,\verb.<.\textit{nonterminal}\verb.>.$  
$\displaystyle\verb.<.\textit{nonterminal}\verb.>.$  $\displaystyle::=$  $\displaystyle\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 Type3 grammars in the Chomsky hierarchy.
A regular grammar can be represented by a deterministic or nondeterministic 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 contextfree languages, any deterministic or nondeterministic 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\mbox{ is a word in two letters }b% \mbox{ 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 $\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:

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

$\mathcal{R}(\Sigma)$ is closed under settheoretic union, concatenation, and Kleene star operations.
Then $L$ is a regular language over $\Sigma$ iff $L\in\mathcal{R}(\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 nonterminal 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.
References
 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
Mathematics Subject Classification
68Q45 no label found68Q42 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections