Regular Language - Deciding Whether A Language Is Regular

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

uwL if and only if vwL 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)

    There is no such thing as a language, not if a language is anything like what many philosophers and linguists have supposed. There is therefore no such thing to be learned, mastered, or born with. We must give up the idea of a clearly defined shared structure which language-users acquire and then apply to cases.
    Donald Davidson (b. 1917)

    [I]n our country economy, letter writing is an hors d’oeuvre. It is no part of the regular routine of the day.
    Thomas Jefferson (1743–1826)