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 (69k points)
edited ago by | 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 

4 Answers

+34 votes
Best answer

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

Option C.

answered by Veteran (346k points)
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. 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.
+11 votes

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

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.


answered by Loyal (4.5k points)

@Arunav Khare Thank you!

regular intersection with any language X is X only ...
+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 (791 points)
+2 votes
Intersection of CFL and regular is always CFL. so option C
answered by Boss (7.8k points)

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

33,687 questions
40,231 answers
38,803 users