529 views

Given the following two statements:

1. $L=\{w\mid n_{a}(w)=n_{b}(w)\}$ is deterministic context free language, but not linear.
2. $L=\{a^{n}b^{n}\} \cup \{a^{n}b^{2n} \}$ is linear, but not deterministic context free language.

Which of the following options is correct?

1. Both (A) and (B) are false.
2. Both (A) and (B) are true.
3. (A) is true, (B) is false.
4. (A) is false, (B) is true.

Ans: B Both I and II are true

L={w∣na(w)=nb(w)}L={w∣na(w)=nb(w)}

is deterministic context free language, but not linear.

L={anbn}∪{anb2n}L={anbn}∪{anb2n}

is linear, but not deterministic context free language.

ref: peter linz

(it is an snapshot of peter linz book.  page no. 306)

Can you tell how 'A' is not linear?
Can anyone provide the link to study  relation b/w CFL , Regular, DCFL, & Linear languages, It would be really helpful.
@pass_i0n

the grammar for A is

S → SS|∈|aSb|bSa , so here production S → SS has two non terminals or variables on right side.

but “A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without restriction on the position of this variable”
L={anbn}∪{anb2n}  is DCFL  and  L={w∣na(w)=nb(w)} is CFL  so  both are false