3,453 views

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

### 1 comment

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

### 1 comment

L1 will be dcfL right ??? Please clarify ...and correct me if I am wrong

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.

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

by

l1 should be cfl ryt??
edited by
yea,you're right. Updated the answer. Thanks for pointing it out.

can u please explain how is anbn for n<100 regular?

as it is said n is less than 100, so it means the language will be finite i.e largest string is a^100b^100.

now for every finite language we can build a finite automata no matter how many states it will take.

so if finite automata exists it will be regular.

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 }

1
1 vote
2
719 views
3