The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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

- Not recursive
- Regular
- Context free but not regular
- Recursively enumerable but not context free.

+34 votes

Best answer

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

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.

+11 votes

$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!

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,271 comments

38,803 users