The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 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.
asked in Theory of Computation by Veteran (59.4k points)
edited by | 1.9k 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 

how is it C?
Yes ,they given option C is the answer.
L = $a^m b^m c \ | \ m \geq 0$ so CFL right?
L1={$a^m$$b^m$c $a^n$$b^n$|m,n>=0}-CFL

L2={$a^i$$b^j$$c^k$|I,j, k>=0}-regular

$L1\cap L2$  - CFL
Why you ignore a^ n b^ n?
Cfl is not close under intersection.
Cfl is closed under intersection with regular language.
Option C : cfl but not regular.

Main doubt is here.

L1 is cfl but regular also. Isn't it?

L2 is regular.

Given option statement I think is doubtful.

L1 is CFL But not reguler.
Why not L1 is regular?

From definition of L1 it seems there is no relation between the power of exponent i.e. m and n. and c can be act as mid symbol.

Correct me if I am wrong.
Can you tell me this language is regular or cfl???

L={a^nb^n /n>o}
Please consider any language as set of strings and see which all strings come in it. If one tried to deduce from just the language description negative mark is sure for GATE.
Then what approach we consider? Make fsa within limited period of time to solve for 2 or 1 mark question. why language definition is given?
@ abhishekmehta4u your given question's answer is cfl not regular.
Simillary L1 is CFL .

there is one comparision between a and b we so we need one stack(pda).
Yes, now I can understand my mistake. thanks.

It will be CFl because 

L1 is generating equal number of a's and b's 

L2 is generating random number of a's b's and c's

so it is evident that set of strings generated by L1 are subset of string generated by L2 .( we wont consider anbn part of L1 as it wont be a part of intersection).

and so intersetion will produce CFL


5 Answers

+13 votes
Best answer

Answer 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).

answered by Active (4.8k points)
edited by

@Arunav Khare Thank you!

regular intersection with any language X is X only ...
+36 votes

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

Option C.

answered by Veteran (342k points)
edited 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. sad

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.
+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.

answered by Junior (801 points)
+2 votes
Intersection of CFL and regular is always CFL. so option C
answered by Loyal (7k points)
+1 vote

Option c is right.

answered by Boss (12.9k points)
This answer is quite similar with Gradup given explanation in their answer.But my doubt is still same.
Any doubt in this solution??
Yes, i have doubt in this solution as same as Gradup answer logic.

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


Here L1 gives like string

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

L2 gives like string 


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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,526 questions
42,803 answers
42,166 users