Deciding Whether A Language Is Regular
To locate the regular languages in the Chomsky hierarchy, one notices that every regular language is context-free. The converse is not true: for example the language consisting of all strings having the same number of a's as b's is context-free but not regular. To prove that a language such as this is regular, one often uses the Myhill–Nerode theorem or the pumping lemma among other methods.
There are two purely algebraic approaches to define regular languages. If:
- Σ is a finite alphabet,
- Σ* denotes the free monoid over Σ consisting of all strings over Σ,
- f : Σ* → M is a monoid homomorphism where M is a finite monoid,
- S is a subset of M
then the set is regular. Every regular language arises in this fashion.
If L is any subset of Σ*, one defines an equivalence relation ~ (called the syntactic relation) on Σ* as follows: u ~ v is defined to mean
- uw ∈ L if and only if vw ∈ L for all w ∈ Σ*
The language L is regular if and only if the number of equivalence classes of ~ is finite (A proof of this is provided in the article on the syntactic monoid). When a language is regular, then the number of equivalence classes is equal to the number of states of the minimal deterministic finite automaton accepting L.
A similar set of statements can be formulated for a monoid . In this case, equivalence over M leads to the concept of a recognizable language.
Read more about this topic: Regular Language
Famous quotes containing the words deciding, language and/or regular:
“During the late war [the American Revolution] I had an infallible rule for deciding what [Great Britain] would do on every occasion. It was, to consider what they ought to do, and to take the reverse of that as what they would assuredly do, and I can say with truth that I was never deceived.”
—Thomas Jefferson (1743–1826)
“UG [universal grammar] may be regarded as a characterization of the genetically determined language faculty. One may think of this faculty as a ‘language acquisition device,’ an innate component of the human mind that yields a particular language through interaction with present experience, a device that converts experience into a system of knowledge attained: knowledge of one or another language.”
—Noam Chomsky (b. 1928)
“This is the frost coming out of the ground; this is Spring. It precedes the green and flowery spring, as mythology precedes regular poetry. I know of nothing more purgative of winter fumes and indigestions. It convinces me that Earth is still in her swaddling-clothes, and stretches forth baby fingers on every side.”
—Henry David Thoreau (1817–1862)