UGC NET CSE | January 2017 | Part 3 | Question: 61

Question

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?

• A. Both (i) and (ii) are false.
• B. Both (i) and (ii) are true.
• C. (i) is true, (ii) is false.
• D. (i) is false, (ii) is true.

Answer 1

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)

Comments

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”

Answer 2

L={anbn}∪{anb2n}  is DCFL  and  L={w∣na(w)=nb(w)} is CFL  so  both are false