recategorized by
4,100 views
2 votes
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?

  1. Both $L_1$ and $L_2$ are not context free language
  2. Both $L_1$ and $L_2$ are context free language
  3. $L_1$ is context free language, $L_2$ is not context free language
  4. $L_1$ is not context free language, $L_2$ is context free language
recategorized by

5 Answers

Best answer
1 votes
1 votes

L1 we can decompose as anbn |n<100 and  anbn|n>100 

First part regular ,second part DCFL , so it is obviously CFL

L2 needs two comparison n(a)= n(b) again n(b)=n(c) so we can not make a PDA for this

so it is CSL but not Context Free

C is correct answer here

selected by
1 votes
1 votes

Correct Option is (3) L1 is context free language, L2 is not context free language.

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 complementintersection, or difference. This was proved by Scheinberg in 1960.[6] However, if L is a context-free language and D is 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.

edited by
0 votes
0 votes

L1: It can be written as {anbn|n<100},this is regular U {anbn|n>100},this is CFL. so resultant language is CFL.

L2:a,b and c can be in any order and most importantly n(a) = n(b) = n(c),so 3 number has to check. It's clearly not CFL.

Option c

edited by
0 votes
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 }

Answer:

Related questions

1 votes
1 votes
7 answers
2
go_editor asked Mar 24, 2020
1,450 views
Consider the languages $L_{1}= \phi$ and $L_{2}=\{1\}$. Which one of the following represents $L_{1}^{\ast}\cup L_{2}^{\ast} L_{1}^{\ast}$?$\{\in \}$$\{\in,1\}$$\phi$$1^{...