regular language

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


where A,B are non-terminal symbols, u,v are terminal words, and λ the empty wordPlanetmathPlanetmathPlanetmath. In BNF, they are:

<non-terminal> ::= terminal
<non-terminal> ::= terminal<non-terminal>
<non-terminal> ::= λ

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 deterministicMathworldPlanetmath or non-deterministic finite automaton. Such automata can serve to either generate or accept sentencesMathworldPlanetmath 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 expressionsMathworldPlanetmath. 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(bc)*a is the set

{a}{b,c}*{a}={awaw is a word in two letters b and c},

where is the concatenationMathworldPlanetmath operationMathworldPlanetmath, and * is the Kleene star operation. Note that w could be the empty word λ.

Yet another way of describing a regular language is as follows: take any alphabet Σ. Let (Σ) be the smallest subset of P(Σ*) (the power setMathworldPlanetmath of the set of words over Σ, in other words, the set of languagesPlanetmathPlanetmath over Σ), among all subsets of P(Σ*) with the following properties:

  • (Σ) contains all sets of cardinality no more than 1 (i.e., and singletons);

  • (Σ) is closed under set-theoretic union, concatenation, and Kleene star operations.

Then L is a regular language over Σ iff L(Σ).

Normal form. Every regular language can be generated by a grammar whose productions are either of the form AaB or of the form Aλ, 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 AaB.

Remark. Closure properties on the family of regular languages are: union, intersectionMathworldPlanetmath, complementation, set differenceMathworldPlanetmath, concatenation, Kleene star, homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath, inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath homomorphism, and reversal.


  • 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 2013-03-22 12:26:31
Last modified on 2013-03-22 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 type-3 language
Synonym type-3 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