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

Suppose you know that the leftmost derivation of
* w* in

*All information is given*

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

*Upvote for the right answer!!*

*Thanks*

Answer #1

**ANSWER:**

- Starting with a single nonterminal 'S' and
- form the string by making substitutions according to the rules.
- Each rule of the form A -->BC adds a new nonterminal
- and each rule of the form A-->a converts one nonterminal into a terminal .
- 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.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 11 minutes ago

asked 14 minutes ago

asked 20 minutes ago

asked 27 minutes ago

asked 30 minutes ago

asked 31 minutes ago

asked 41 minutes ago

asked 43 minutes ago

asked 46 minutes ago

asked 53 minutes ago

asked 55 minutes ago

asked 56 minutes ago