TULA

TULA

Dayeong Kang

How to identify if a language is regular or not

Learn about regular languages first and identify regularity of the languages.

What is regular languages?

A regular language (also called a rational language) is a formal language that can be defined by a regular expression. Then, what is the regular expression (REGEX)? It uses a given alphabet (Σ), arithmetic expressions (+, •, _), and primitive regular expressions (Ø, λ). If r1 and r2 are regular expressions (REXs), r1 + r2, r1 • r2, and r1_ are also regular ones.

  • Every regular language L(r) has a REGEX r.
  • Every REGEX r has a regular language L(r).

REXs have NFA (or DFA). Conversion proceeds with a generalized transition graph (GTG).

  • Every REGEX can build NFA (or DFA).
  • NFA (or DFA) can make REXs.

A GTG must be a complete one which all edges are present, so missing edges should be defined as undefined (Ø). From every GTG with more than two states, we can also find an arbitary GTG: a GTG with only two states. The remains are the initial state and a final state.

In the previous post, I mentioned that languages’ definition is a little bit ambiguous itself so it needs grammars. A regular language also has a regular grammar. Regular grammars must be right or left linear and they can make NFA (or DFA).

In conclusion:

  1. A regular language are empty, finite, or infinite.
  2. Every empty and finite one is regular. (They can make NFA (or DFA).)
  3. REXs ⇔ NFA (or DFA) ⇔ Regular grammars

Example: find a REGEX for language L

L = {w ∈ {0, 1}*: w has no pair of consecutive zeros}

r = (1 + 01)*(0 + λ)

The image below is an automaton M(r) accepts L((1 + 01)*(0 + λ)).

nfa

Find non-regular languages: pumping lemma

Regular languages are empty, finite, or infinite, but not all infinite ones are regular. We need a method to figure infinite non-regular languages out: pumping lemma.

Let L be an infinite regular language. Then there exists some positive m such that any w ∈ L with $|w| \geq m$ can be decomposed as $w = xyz$ with $|xy| \leq m$ and $|y| \geq 1$ such that $w_{i} = xy^iz$ is also in L for i = 0, 1, 2, … While i keeps growing, if there is only one value of i that does not fit to the language definition, the language is not regular and it is called y cannot be “pumped”. Therefore, we can determine only non-regular languages with pumping lemma, not regular ones.

References

💬 Any comments and suggestions will be appreciated.

Leave a comment

You may also enjoy