CODEWITHSUNDEEP
regular-language
Jonathan Lam
Jonathan Lam

Reputation: 185

Proving Regular Languages

I have to prove this statement is false. If L1 = {ab| a∈L2, b∉L2} is a regular language, then L2 is a regular language.

(a and b are strings.) (Assume L1 and L2 have the same alphabets.)

My work:
The question can be rewritten as: if L2 is regular, then L1 is non-regular. (Prove this is true)

proof by contrapositive: If L2 is regular, then L1={ab| a∈L2, b∉L2} is non-regular

I'm not sure what to do after this line. Is that the right approach? Can someone give me some hints on how to do this?

Upvotes: 1

Views: 310

Answers (1)

John Kugelman
John Kugelman

Reputation: 361585

Let A = "L1 = {ab| a∈L2, b∉L2} is a regular language".
Let B = "L2 is a regular language".

The problem is to prove that A → B is false. This is equivalent to proving A ∧ ¬B. Which in English, reads:

L1 = {ab| a∈L2, b∉L2} is a regular language but L2 is not a regular language.

So one tactic might be to find a non-regular L2 which leads to L1 being regular. If you can do that then you have a counter-example and so you've proven the original statement false.

Upvotes: 1

Related Questions