in Theory of Computation
493 views
1 vote
1 vote
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$
in Theory of Computation
by
493 views

1 Answer

0 votes
0 votes
Formally, we can prove by Induction , but let me give you an intuitive idea.
There are two types of derivations , one which is of the form A$\rightarrow$TD and A$\rightarrow$b.

To generate a string of length we need n-1 derivations of the form A$\rightarrow$TD. And to finally replace the non-terminals , we need n productions of the form A$\rightarrow$b to replace each non-terminal to a terminal.

 Hence, we need n-1+n=2n-1 productions in all exactly , to get a string of length n.

Related questions