regular language (original) (raw)

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 word. In BNF, they are:

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.

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

• •
• •
  ℛ⁢(Σ) 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 A→a⁢B 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 A→a⁢B.

References

• 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).