Simple Grammar

Question

Consider Grammar G with the following characteristic-

$A → ax$, where $A ∈ V$, $a ∈ T$, $x ∈ V^*$, and any pair $( A, a )$ occurs at most once in $P$. For example, $S → aA \mid aB...,$ is not a grammar of type $G$ because the pair $(S,a)$ occur in two productions. Which of the following is proportional to the effort required to parse a string w belonging to $L(G)$ ?

• A. $\mid w \mid^3$
• B. $\mid w \mid$
• C. $2^{\mid w \mid}$
• D. Not a function of $\mid w \mid$ alone.

Answer 1

Ans-B

As any (A,a) pair occurs only once... we can reduce any variable to terminal at each step. So parsing this type of grammar will require effort equal to length of string.

Answer 2

Hope this helps.