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
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.