Formal Definition
The collection of regular languages over an alphabet Σ is defined recursively as follows:
- The empty 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 A ∪ B (union), A • B (concatenation), and A* (Kleene star) are regular languages.
- No other languages over Σ are regular.
See regular expression for its syntax and semantics. Note that the above cases are in effect the defining rules of regular expression.
- Examples
All finite languages are regular; in particular the empty string language {ε} = Ø* is 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 . Intuitively, it cannot be recognized with a finite automaton, since a finite automaton has finite memory and it cannot remember the exact number of a's. Techniques to prove this fact rigorously are given below.
Read more about this topic: Regular Language
Famous quotes containing the words formal and/or definition:
“That anger can be expressed through words and non-destructive activities; that promises are intended to be kept; that cleanliness and good eating habits are aspects of self-esteem; that compassion is an attribute to be prized—all these lessons are ones children can learn far more readily through the living example of their parents than they ever can through formal instruction.”
—Fred Rogers (20th century)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)