Regular language

related topics
{math, number, function}
{language, word, form}

In theoretical computer science, a regular language is a formal language (i.e., a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties:

Contents

Regular languages

The collection of regular languages over an alphabet Σ is defined recursively as follows:

  • the empty language Ø is a regular language.
  • the empty string language { ε } is a regular language.
  • For each a ∈ Σ (a belongs to Σ ), the singleton language { a } is a regular language.
  • If A and B are regular languages, then AB (union), AB (concatenation), and A* (Kleene star) are regular languages.
  • No other languages over Σ are regular.

All finite languages are regular. Other typical examples include the language consisting of all strings over the alphabet {a, b} which contain an even number of as, or the language consisting of all strings of the form: several as followed by several bs.

A simple example of a language that is not regular is the set of strings \{a^nb^n\,\vert\; n\ge 0\}.

Full article ▸

related documents
Amicable number
Kernel (category theory)
Goldbach's weak conjecture
Metrization theorem
Ordered field
Topological ring
Twin prime conjecture
Lipschitz continuity
Graded algebra
Separated sets
Magma (algebra)
Logical disjunction
Greedy algorithm
Complement (set theory)
Binary function
Divisor
Lagrange's theorem (group theory)
CLU (programming language)
Heaviside step function
Simple LR parser
Polynomial time
Bézout's identity
Chomsky normal form
Intersection (set theory)
NP-hard
Uncountable set
Nash embedding theorem
Euler's criterion
Syntactic sugar
BPP