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:
“It has often been argued that absolute scepticism is self-contradictory; but this is a mistake: and even if it were not so, it would be no argument against the absolute sceptic, inasmuch as he does not admit that no contradictory propositions are true. Indeed, it would be impossible to move such a man, for his scepticism consists in considering every argument and never deciding upon its validity; he would, therefore, act in this way in reference to the arguments brought against him.”
—Charles Sanders Peirce (1839–1914)
“Which I wish to remark—
And my language is plain—
That for ways that are dark
And for tricks that are vain,
The heathen Chinee is peculiar:
Which the same I would rise to explain.”
—Bret Harte (1836–1902)
“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)