recategorized by
1,926 views
3 votes
3 votes

For every context free grammar (G) there exists an algorithm that passes any $w \in L(G)$ in number of steps proportional to

  1. $ln\mid w \mid$
  2. $\mid w \mid$
  3. $\mid w \mid^2$
  4. $\mid w \mid^3$
recategorized by

1 Answer

Answer:

Related questions

2 votes
2 votes
1 answer
2
go_editor asked Jul 17, 2016
1,456 views
Match the following :$\begin{array} {} \text{a.}& \text{Context sensitive language} & \text{i.} & \text{Deterministic finite automation} \\ \text{b.}& \text{Regular gram...
4 votes
4 votes
2 answers
4
go_editor asked Jul 17, 2016
2,628 views
The grammar with production rules $S \rightarrow aSb \mid SS \mid \lambda$ generates language $L$ given by:$L = \{ w \in \{a, b\}* \mid n_a(w) = n_b(w) \text{ and } n_a(v...