Dark Mode

3,402 views

2 votes

Given the following two languages:

$L_1 = \{a^n b^n \mid n \geq 0, \: n \neq 100\}$

$L_2 = \{ w \in \{a, b, c\}^* \mid n_a(w) = n_b (w) = n_c(w) \}$

Which of the following options is correct?

- Both $L_1$ and $L_2$ are not context free language
- Both $L_1$ and $L_2$ are context free language
- $L_1$ is context free language, $L_2$ is not context free language
- $L_1$ is not context free language, $L_2$ is context free language

1 vote

Best answer

1 vote

Correct Option is **(3) L _{1} is **

For $L_{1}$, consider the languages $L_{11} = \{ a^{n}b^{n} \}$ and $L_{12} = \{ a^{100} b^{100} \}$.

Here, $L_{11}$ is DCFL, and $L_{12}$ is regular. So their difference (i.e. $L_{11} \setminus L_{12}$) is context free.

Context-free languages are not closed under complement, intersection, or difference. This was proved by Scheinberg in 1960.

^{[6]}However, ifLis a context-free language andDis a regular language then both their intersection {$ L\cap D$} and their difference {$L\setminus D$} are context-free languages.

This is from Wikipedia.

The given language $L_1$ is nothing but $L_{11} \setminus L_{12}$. Hence, it is context free.

For $L_2$, we need to compare the number of a's, b's and c's which cannot be done by a pushdown automaton. Hence, it is not context free.

0 votes

**L1 is not context free language, L2 is context free language**

**L1={ ${ a^{n}b^{n},∣ n≥0,n≠100}$}**

**here variable n has two comparisons n≠100 and equal number of a and b so not context free**

**L2={${w∈{(a,b,c)}^{∗}∣ na(w)=nb(w)=nc(w)}$}**

**it is not context free number of comparisons more than 1 ,equal number of a,b,c{a=b and b=c }**