1.7k views

Let $L = L_1 \cap L_2$, where $L_1$ and $L_2$ are languages as defined below:

$L_1= \left \{ a^m b^mca^nb^n \mid m,n \geq 0 \right \}$

$L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$

Then $L$ is

1. Not recursive
2. Regular
3. Context free but not regular
4. Recursively enumerable but not context free.

edited ago | 1.7k views

here L1 is CFL  but not regular, L2 is regular so  CFL  now

CFL are closed under intersection with regular languages so L =  L2∩L1 is CFL  what is wrong in his approach , L can be regular only when  L2 and L1 both are regular so why to  consider option (b) . It is simply option C

$L_1 \cap L_2 = \{a^mb^mc | m \geq 0\}$, which is context free but not regular.

Option C.

edited ago by

L1 ∩ L2={ambmc}

Not regular

:O ?
Correction in que.. L1={a^mb^mc a^nb^n|m,n>=0}

why is intersection {c} and not L1 ∩ L2={ambmc} ?? @Arjun

When we intersect two sets, we get the COMMON elements in both.

Yes...saw my mistake I did not notice that the second b is b^m and not n. Thanks :)

I found that too by expanding the language and only c is common and i ticked regular but answer given is CFG. Donno y.

Arjun sir, what is the method to generate L1∩L2? That is how are you saying the language of  L1∩L2?
@ Arjun Sir,

Please point out what is wrong in this process.

L1 is DCFL and L2 is regular. This means both are CFL and $L=L1\cap L2$  is not CFL since CFL is not closed under intersection. So L is recursive but not context free.

is not CFL since CFL is not closed under intersection

I do not know who is spreading such a meaning for "not closed". Does some coaching institute teach so? Doeas some book has such a statement? See if it rains, we get wet- > does not mean that if it does not rain we won't get wet.

Not closed $\equiv$ We can't say.

CFL is not closed under intersection means we can't say what we get when we intersect two CFLs.
Thanks @Arjun Sir and @Sachin for the update.

$L_1= \left \{ a^m b^mca^nb^n \mid m,n \geq 0 \right \}$

It is a CFL. It will generate strings which start with a's followed by equal number of b's and single c followed by a's followed by equal number of b's

Eg: ${abcab, aabbcab, aaabbbcaabaabb ....}$

$L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$

It is a Regular (and of course CFL). It will generate strings which begin with a's followed by any number of b's followed by any number of c's

So, $L_1 \bigcap L_2$ will be all strings which are common in both languages

So, those will be the strings which begin with a's followed by equal number of b's and ending with c

They would be of the form $a^mb^mc$

Such a language is not regular. It is Context Free language.

@Arunav Khare Thank you!

regular intersection with any language X is X only ...

The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, …} and L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }. Intersection of these two languages is L1 ⋂ L2 = {a{k}b{k}c | k >= 0} which is context free, but not regular.

Intersection of CFL and regular is always CFL. so option C