edited by
9,738 views
38 votes
38 votes

Let $L$ be a context-free language and $M$ a regular language. Then the language $L ∩ M$ is

  1. always regular
  2. never regular
  3. always a deterministic context-free language
  4. always a context-free language
edited by

6 Answers

Best answer
52 votes
52 votes

Let $\Sigma=\{a,b\}.$
$L_1 = \Sigma^*$ is a regular language
$L_2 = \{ww^R \mid w \in (a+b)^*\}$ is a context free language.
$L_1\cap L_2 = \{ww^R \mid w \in (a+b)^*\}$  which is clearly context free language and not DCFL or Regular
Hence, the answer is option D.

edited by
8 votes
8 votes

Eliminate each option by throwing a counter example

L –  Context free language, M – Regular language

A) always regular

$L$ - {$a^{n}b^{n}$}

$R$ - {$a^{*}b^{*}$}

$L \cap R$ = {$a^{n}b^{n}$}, which is not regular

Therefore, A) is False

B) Never regular

$L$ = { }

$R$ = { }

$L \cap R$ = { }, which is regular

Therefore B) is False

C)  always a deterministic context-free language

$L$ - $\left \{ ww^{r}, w\in \left \{ a,b \right \}^{*} \right \}$

$R$ - $\left \{ (a+b)^{*} \right \}$

$L \cap R$ =$\left \{ ww^{r}, w\in \left \{ a,b \right \}^{*} \right \}$, which is non-deterministic CFL

Therefore, C) is False

So, Option D is True

 

Actually, to come to a conclusion of “always correct”, you need to come up with the proof. You can’t just show one example as “correct” and come to a conclusion of “always correct”.

But you can come to a conclusion of “not always correct” by just throwing a counter example which tells as “not correct”.

6 votes
6 votes
It is always a cfl.i really never heard it to be dcfl which is less powerful than cfl
3 votes
3 votes
  1. Any Language (say L1)  $ \bigcap$ Regular language = L1 always. 
  2. Any language (L2) $\cup$ Regular language = L2 always 

Hence option D. 

Answer:

Related questions

29 votes
29 votes
1 answer
1
Ishrat Jahan asked Oct 31, 2014
7,898 views
Which of the following statements about regular languages is NOT true ?Every language has a regular supersetEvery language has a regular subsetEvery subset of a regular l...