# Simple Grammar

1 vote
748 views

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)$ ?

1. $\mid w \mid^3$
2. $\mid w \mid$
3. $2^{\mid w \mid}$
4. Not a function of $\mid w \mid$ alone.

edited

1 vote

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.

edited

Hope this helps. ## Related questions

1
239 views
Consider a push down automata (PDA) below which runs over the input alphabet (a, b). It has the stack alphabet {z0, X}, where z0 is the bottom of stack marker. The set of states of PDA is {q0,q1} where q0 is the start state and rules of the PDA are, (The languare accepted by the grammar is)
1 vote
how $a^nb^nc^n$ n>=1 is not CFL....??