in Theory of Computation edited by
12,920 views
48 votes
48 votes

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.
in Theory of Computation edited by
12.9k views

4 Comments

DCFL are closed under intersection with regular languages.
0
0
sir,  when L1 is cfl=>  Because Read input a, push into stack; seen ‘b’ pop ‘a’; seen c skip, again Read input a, push into stack; seen ‘b’ pop ‘a’; using (dpda)and L2 is Regular Because, easily construct DFA =>first take FOUR states to construct dfa  1,2,3,d; seen ‘a’ looping  on 1, other than ‘a’ goto dead state, seen b goto the state 2 any number of b looping on 2, if ‘a’ come to here then go to dead state, if ‘C’ is coming then go to state 3, in here a or b come goto dead state.  L=L1 intersection L2. so, L is cfl.
1
1

@Ajitgate21 When actual languages are given, it’s better not to use closure property but to work out the language itself and check what type of language it is.

1
1

6 Answers

43 votes
43 votes
Best answer

Answer is C.

$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

i.e., ${abcab, aabbcab, aaabbbcaabaabb, \ldots}$

$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 \cap 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 as it requires equal number of a's and b's. But it is Context Free language as we can make a PDA for it. Also, CFLs are closed under intersection with regular set. So, any CFL intersection a regular set gives a CFL (may or may not be a regular set).

edited by

3 Comments

@Arunav Khare Thank you!

2
2
regular intersection with any language X is X only ...
2
2
It was really a nice way to solve . The question could be solved using properties directly but what more important is how to approach a question in  many ways. Thanks for the explanation 🙏🏻
1
1
44 votes
44 votes

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

Option C.

edited by
by

4 Comments

Thanks @Arjun Sir and @Sachin for the update.
0
0
sir please tell me whats wrong in this approach!

L1 contains all the strings that end with b's

L2 contains all the strings that end with c.

now ,

L=L1∩L2 = phi

since phi is regular. therefore option b
0
0

@ Would've been phi if it was $a^{m}b^{m}ca^{m}b^{m}$.. But since last a and b are powers of n and n can be 0.. Right?

0
0
6 votes
6 votes

Option c is right.

4 Comments

This answer is quite similar with Gradup given explanation in their answer.But my doubt is still same.
0
0
Any doubt in this solution??
0
0
Yes, i have doubt in this solution as same as Gradup answer logic.

L1 intersection L2={a^ m b^ m c|m>=0}

Why?
0
0

Here L1 gives like string

{abc,aabbc,aaabbbc, abcab.......} 

L2 gives like string 

{abc,aabbc,aabbcc,.............}

try to understand both language in

  • L1 it gives only one c . So comman string must be only one c.
  • In L2 a follow b and b follow c .

So comman string like abc,aabbc... So on

1
1
2 votes
2 votes

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.

Answer:

Related questions