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)
“To write or even speak English is not a science but an art. There are no reliable words.... Whoever writes English is involved in a struggle that never lets up even for a sentence. He is struggling against vagueness, against obscurity, against the lure of the decorative adjective, against the encroachment of Latin and Greek, and, above all, against the worn-out phrases and dead metaphors with which the language is cluttered up.”
—George Orwell (1903–1950)
“My attitude toward punctuation is that it ought to be as conventional as possible. The game of golf would lose a good deal if croquet mallets and billiard cues were allowed on the putting green. You ought to be able to show that you can do it a good deal better than anyone else with the regular tools before you have a license to bring in your own improvements.”
—Ernest Hemingway (1899–1961)