Pumping Lemma For Regular Grammars

Posted By on April 29, 2016


Download PDF
Chomsky Classification of Grammars
DFA Complement

Pumping Lemma for Regular Languages

Theorem

Let L be a regular language. Then there exists a constant ‘c’ such that for every string w in L

|w| ≥ c

We can break w into three strings, w = xyz, such that −

  • |y| > 0
  • |xy| ≤ c
  • For all k ≥ 0, the string xykz is also in L.

Applications of Pumping Lemma

Pumping Lemma is to be applied to show that certain languages are not regular. It should never be used to show a language is regular.

  • If L is regular, it satisfies Pumping Lemma.
  • If L is non-regular, it does not satisfy Pumping Lemma.

Method to prove that a language L is not regular

  • At first, we have to assume that L is regular.
  • So, the pumping lemma should hold for L.
  • Use the pumping lemma to obtain a contradiction −
    • Select w such that |w| ≥ c
    • Select y such that |y| ≥ 1
    • Select x such that |xy| ≤ c
    • Assign the remaining string to z.
    • Select k such that the resulting string is not in L.

Hence L is not regular.

Problem

Prove that L = {aibi | i ≥ 0} is not regular.

Solution

  • At first, we assume that L is regular and n is the number of states.
  • Let w = anbn. Thus |w| = 2n ≥ n.
  • By pumping lemma, let w = xyz, where |xy|≤ n.
  • Let x = ap, y = aq, and z = arbn, where p + q + r = n.p ≠ 0, q ≠ 0, r ≠ 0. Thus |y|≠ 0
  • Let k = 2. Then xy2z = apa2qarbn.
  • Number of as = (p + 2q + r) = (p + q + r) + q = n + q
  • Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.
  • Thus, xy2z is not in L. Hence L is not regular.

Complement of a DFA

If (Q, ∑, δ, q0, F) be a DFA that accepts a language L, then the complement of the DFA can be obtained by swapping its accepting states with its non-accepting states and vice versa.

We will take an example and elaborate this below −

DFA Accepting Language L

This DFA accepts the language

L = {a, aa, aaa , …………. }

over the alphabet

∑ = {a, b}

So, RE = a+.

Now we will swap its accepting states with its non-accepting states and vice versa and will get the following −

DFA Accepting Complement Language L

This DFA accepts the language

Ľ = { ε , b, ab ,bb,ba, …………… }

over the alphabet

∑ = {a, b}

Note − If we want to complement an NFA, we have to first convert it to DFA and then have to swap states as in the previous method.

Chomsky Classification of Grammars
DFA Complement

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com