#theory-of-computation

Question

If L1 = {a^nb^nc^md^m | n,m>=0}

L2 = {a^nb^n | n>=0}

L3 = {c^md^m | m>=0}

Then L1 – L2.L3(concatenation) is?

• A. Regular
• B. CSL
• C. CFL
• D. REL(recursive enumerable)

Comments

CSL ??

L2.L3=CFL & L1=CFL

SO L1-L2.L3=CFL $\bigcap$ (CFL)COMPLEMENT 

SO CFL$\bigcap$ CSL=CSL

 

---

As per me, this is CSL, which is a subset of REL so correct answers are both (B) and (D).

But the answer says all options are true. I think that is wrong.

---

Whenever language is given we have to work according to language.

Answer 1

Given,

L1 = {a^n b^n c^m d^m | n, m>=0} = {ɛ, ab, cd, abcd, aabb, ccdd,…..}

L2 = {a^n b^n | n>=0} = {ɛ, ab, aabb, aaabbb, …..}

L3 = {c^m d^m | m>=0} = {ɛ, cd, ccdd, cccddd, …..}

 

Now, L2.L3 = {ɛ, ab, aabb, aaabbb, …..} . {ɛ, cd, ccdd, cccddd, …..}

 = {ɛ, ab, cd, abcd, aabb, ccdd, aabbcd, aabbccdd ….}

see, L2.L3 contain all the element which is present in L1

so, L1 – L2.L3 = {} (empty set) which is regular

As L1 – L2.L3 is regular so its CFL, CSL, REL

Hence all option is correct