1
$\begingroup$

I am still learning the pumping lemma. I have a problem for which I used it. I used it on the first part (a) but I am unsure if it is correct.

Parts b-d, I am not sure how to do it. I created a dfa for L2, therefore it is regular. But for part b and c, it is asking about the union and intersection and I am unsure how to do that with a regular language(L2) and a non-regular language(L1). For part d, I am not sure how to go about it at all.If anyone can please take a look at it and let me know/give me some advice, I'd really appreciate it.

Thank you.

Let ∑ = {a,b} and L1 = { a^k b^k:k ≥ 3 } and L2 = {a^k b^n: k ≥ 0, n ≥ 0} Determine if the following languages are regular or not regular. Give complete arguments proving your answers.

a)L1

b)L1 ∪ L2

c)L1 ∩ L2

d)L2 - {λ, ab, a^2 b^2}


a)[using Pumping lemma]

Let L = { a^k b^k:k ≥ 3 }. Assume L is regular. Let m be the number from the pumping lemma. Let s = a^m b^m. Since s ∈ L and |s| ≥ m, the pumping lemma must apply, specifically,

s = xyz where y ≠ λ and |xy| ≤ m.

y = a^k where 0 < k ≤ m

x = a^q where 3 ≤ q < m

z = a^(m-k-q) b^m

xyyz = a^q a^k a^k a^(m-k-q)b^m

= a^(k+m)b^m ∉ L

Thus our assumption that L is regular must not be true. Thus L must not be regular.

$\endgroup$

1 Answer 1

1
$\begingroup$

HINT: $L_1\cup L_2=L_2$, and $L_1\cap L_2=L_1$. For (d), note that you can design a DFA that handles the members of any finite collection of words, like $\{\lambda,ab,a^2b^2\}$, individually, and handles all other words separately.

Your use of the pumping lemma in (a) is correct.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .