Non-Regular Language, Pumping Lemma

Fatima Hasan · Apr 20, 2018

Homework Statement

Prove that ## L ## is non-regular language.

$Set definition L = {a^n b^k : n > k and n ≥ 0}, written as a set of strings a to the power n followed by b to the power k.$

2. Homework Equations
none

The Attempt at a Solution

Pumping lemma proof setup: text reads 'Assume that L is regular and has pumping length p', 'String a^(p+1)b^p is in L', 'Let p = 7 → S = aaaaaaa bbbbbbbb' with 7 a's and 8 b's labelled, and 'We try to partition S into 3 parts xyz'.

Pumping lemma proof case 1: y in all a's. Strings a^2 a^5 b^8 split into x=2, y=5, z=8, pumped to xy^2z giving 2, 10 and 8 a's and b's, then 12 a's and 8 b's shown not in L, a contradiction.

Pumping lemma proof case 2: y in a's and b's. Strings aaaaa aabb bbbbbb with x=5, y=4, z=6 are pumped to xy^2z, giving aaaaa aabbaabb bbbbbb, which is marked as not in L, a contradiction.

Pumping lemma proof case 3: a string a^7 b^1 b^7 split into x=7 a's, y=1 b, z=7 b's; pumped to xy^2z giving a^7 bb b^7, then a^7 b^9 not in L, a contradiction.

So L is non-regular !
Is my solution correct?

tnich · Apr 20, 2018

Fatima Hasan said:

Homework Statement

Prove that ## L ## is non-regular language.
View attachment 224379

2. Homework Equations
none

The Attempt at a Solution

View attachment 224375

View attachment 224376

View attachment 224377

View attachment 224378

So L is non-regular !
Is my solution correct?

It does appear to be correct. You could simplify it a little by noting that you only need one counter-example to prove a statement false.
Edit: I take that back. I think you are correct to consider all of the cases, since the pumping lemma says a way to divide S into xyz that satisfies the rest of the conditions exists.

Non-Regular Language, Pumping Lemma

Homework Statement

The Attempt at a Solution

Discussion

Homework Statement

The Attempt at a Solution

Similar threads