search
Log In
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.
in Theory of Computation
edited by
748 views

2 Answers

1 vote
 
Best answer

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 by
0 votes

Hope this helps. 

Related questions

0 votes
0 answers
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)
asked Nov 30, 2018 in Theory of Computation rahuljai 239 views
1 vote
1 answer
2
0 votes
3 answers
3
745 views
S->AbaC A->BC B->b/epsilon C->D/epsilon D->d I want to know that will A contain epsilon as B and C both are null variables???(In Elimination of epsilon-production)
asked Nov 30, 2016 in Theory of Computation Anmol Verma 745 views
0 votes
0 answers
4
164 views
consider following grammer S → aSb / aSbb / aSbbb / ….. is language generated by above grammer is DCFL?
asked Dec 24, 2018 in Theory of Computation Rahul_Rathod_ 164 views
...