UGC NET CSE | December 2014 | Part 3 | Question: 23

Question

Given two languages :

$L_{1}=\left\{(ab)^{n} a^{k} | n > k, k \geq 0\right\}$

$L_{2}=\left\{a^{n}b^{m} | n \neq m\right\}$

Using pumping lemma for regular language, it can be shown that 

• A. $L_{1}$ is regular and $L_{2}$ is not regular. 
• B. $L_{1}$ is not regular and $L_{2}$ is regular. 
• C. $L_{1}$ is regular and $L_{2}$ is regular.
• D. $L_{1}$ is not regular and $L_{2}$ is not regular. 

Answer 1

Theorem (Pumping Lemma):
–Let L be a regular language, recognized by a DFA with p states.
–Let x ∈L with |x| ≥p.
–Then x can be written as x = u v w where |v| ≥1, so that for all z ≥0, uv^z w ∈L.
–In fact, it is possible to subdivide x in a particular way, withthe total length of u and v being at most p: | u v | ≤p.
1)assume   (ab)ⁿ b^k  is regular

consider x = abababaa

u =ababab

v = a

w = a

let z = 2

u (a)²w

abababaaa must also belong to L but it can't because n = k here... hence not regular

2)assume aⁿ b^m is regular...

aaaabb

u = aaaa

v= b

w = b

z = 3

u (b)³w

ubbbw

aaaabbbb must also belong to language L but...it doesn't belong bcoz...here n = m...so not regular...hence answer is (d)

Comments

x u chose isn't regular.

---

but pumping lemma can not say that language is regular ,if language is already regular.

pumping lemma is a negatavity test.

so option d is correct.

Answer 2

whenever pumping lemma is there it can only be used to prove that language is not regular or not context free 

so here ans is D L1L1 is not regular and L2L2 is not regular

Comments

but that doesn't mean that 'mr. pumping lemma' always succeeds

---

tat's just a tool to disprove if used 'properly'. & the disprovement holds in our universe of truth.

Answer 3

L1 = {(ab)ⁿa^k|n > k, k ≥ 0}:- Here is comparison between n and k so  that comparison not allowed finite automata so that it not regular language 

L2 = {aⁿb^m|n not equal m}:- here is also comparison between n and m so  it is not regular language