in Theory of Computation recategorized by
3,402 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
in Theory of Computation recategorized by
3.4k views

1 comment

5 Answers

1 vote
1 vote
Best answer

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 comment

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

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
by

4 Comments

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

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

0
0
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.
0
0
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