regular language
A regular grammar is a contextfree grammar where a production has one of the following three forms:
$$A\to \lambda ,A\to u,A\to vB$$ 
where $A,B$ are nonterminal 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 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\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 $\mathcal{R}(\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:

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

•
$\mathcal{R}(\mathrm{\Sigma})$ is closed under settheoretic union, concatenation, and Kleene star operations.
Then $L$ is a regular language over $\mathrm{\Sigma}$ iff $L\in \mathcal{R}(\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 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).
Title  regular language 
Canonical name  RegularLanguage 
Date of creation  20130322 12:26:31 
Last modified on  20130322 12:26:31 
Owner  mps (409) 
Last modified by  mps (409) 
Numerical id  21 
Author  mps (409) 
Entry type  Definition 
Classification  msc 68Q45 
Classification  msc 68Q42 
Synonym  type3 language 
Synonym  type3 grammar 
Synonym  regular set 
Synonym  regular event 
Related topic  Language 
Related topic  DeterministicFiniteAutomaton 
Related topic  NonDeterministicFiniteAutomaton 
Related topic  RegularExpression 
Related topic  KleeneAlgebra 
Related topic  ContextFreeLanguage 
Related topic  KleenesTheorem 
Defines  regular grammar 