edited by
12,979 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.
edited by

6 Answers

Best answer
43 votes
43 votes

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
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
6 votes
6 votes

Option c is right.

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

46 votes
46 votes
7 answers
1
Kathleen asked Sep 22, 2014
20,950 views
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$.end with $0$.end with $00$.contain the substring $00$.
34 votes
34 votes
7 answers
4
Kathleen asked Sep 22, 2014
20,203 views
$$S \to aSa \mid bSb\mid a\mid b$$The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of:all palindromesall odd length palindromesstrings t...