Question

Theory of Computation Problem 3:

Let G be an arbitrary CFG (Context-free Grammer), and let D_G be the string-pushing PDA(pushdown automata) for it. Let w be some string of length n in L(G).

Suppose you know that the leftmost derivation of w in G consists of m substitutions. How many transitions would be in the corresponding computation of D_G for input string w? Justify your answer carefully!

All information is given

-----------------------------------------------------------------

Upvote for the right answer!!

Thanks

Answer 1

ANSWER:

1. Starting with a single nonterminal 'S' and
2. form the string by making substitutions according to the rules.
3. Each rule of the form A -->BC adds a new nonterminal
4. and each rule of the form A-->a converts one nonterminal into a terminal .
5. Since it takes n-1 steps to grow the string from the original nonterminal to n nonterminals ,and then n steps to convert each of those nonterminals into terminals,it takes 2n-1 steps to derive a string of length n.