The Gateway to Computer Science Excellence
0 votes

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 by Active (1.7k points)
edited by | 212 views

2 Answers

0 votes
Best answer


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.

by Active (2.3k points)
edited by
0 votes

Hope this helps. 

by Active (3.5k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
104,903 users