Question

# Theory of Computation Problem 3: Let G be an arbitrary CFG (Context-free Grammer), and let DG...

Theory of Computation Problem 3:

Let G be an arbitrary CFG (Context-free Grammer), and let DG 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 DG for input string w? Justify your answer carefully!

All information is given

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

Upvote for the right answer!!

Thanks

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.

#### Earn Coins

Coins can be redeemed for fabulous gifts.