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:
“Our passional nature not only lawfully may, but must, decide an option between propositions, whenever it is a genuine option that cannot by its nature be decided on intellectual grounds; for to say, under such circumstances, “Do not decide, but leave the question open,” is itself a passional decision—just like deciding yes or no—and is attended with the same risk of losing the truth.”
—William James (1842–1910)
“If when a businessman speaks of minority employment, or air pollution, or poverty, he speaks in the language of a certified public accountant analyzing a corporate balance sheet, who is to know that he understands the human problems behind the statistical ones? If the businessman would stop talking like a computer printout or a page from the corporate annual report, other people would stop thinking he had a cash register for a heart. It is as simple as that—but that isn’t simple.”
—Louis B. Lundborg (1906–1981)
“The solid and well-defined fir-tops, like sharp and regular spearheads, black against the sky, gave a peculiar, dark, and sombre look to the forest.”
—Henry David Thoreau (1817–1862)