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:

    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)

    Man acts as though he were the shaper and master of language, while in fact language remains the master of man.
    Martin Heidegger (1889–1976)

    They were regular in being gay, they learned little things that are things in being gay, they learned many little things that are things in being gay, they were gay every day, they were regular, they were gay, they were gay the same length of time every day, they were gay, they were quite regularly gay.
    Gertrude Stein (1874–1946)