edited by
1,351 views
0 votes
0 votes

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 (i) and (ii) are false.
  2. Both (i) and (ii) are true.
  3. (i) is true, (ii) is false.
  4. (i) is false, (ii) is true.
edited by

2 Answers

1 votes
1 votes

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)

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^{...