# Why can't exhaustive search parsing stop after |w| + 1 derivations?

If my grammar does not have productions of the form $$A\rightarrow\lambda$$ and $$A\rightarrow B$$ for some variables $$A$$ and $$B$$ then I know that each step in the derivation must involve an increase in the sentential length. Therefore if I do an exhaustive search for some word $$w$$ then I know I can stop searching after $$|w|$$ derivations.

My question is why then do textbooks assert that we can stop after $$2|w|$$ derivations instead? Yes, I agree that this is true, but wouldn't it be easier just to stop at $$|w|+1$$ and above? What am I missing for this condition?

• Which textbooks? Nov 2 '18 at 6:37
• "An Introduction to Formal Languages and Automata", Peter Linz Nov 2 '18 at 6:41

## 2 Answers

You increase the length of the sequential form with each derivation, but you also need to convert non-terminals to terminals.

Think of a grammar in Chomsky normal form. For each word symbol, you need to create a non-terminal first (and you create only one per derivation!) and then convert it into a terminal. That's $$2|w| \pm 1$$ derivations right there.

Yes, CNF is a little wasteful this way, but finding short derivations isn't its purpose, isn't it?

Each derivation step replaces applies a production to one non-terminal. After $$|w|-1$$ derivation steps you have a sentential form of length $$|w|$$. You need one derivation to replace each non-terminal with its corresponding terminal. So the total number of steps is $$2|w|-1$$.

• Nice answer. It could be misleading though, since it might be false that "after $|w|-1$ derivation you have $|w|$ length sententia form". For example, $S\Rightarrow AS\Rightarrow aS\Rightarrow aBS\Rightarrow abS\Rightarrow abc$. After 3-1 =2 derivations, the sentential form $aS$ is of length 2. Of course, I know what you meant. I am just nitpicking as what you have written might not be your true idea. You would like to hold yourself to a higher standard when your answer could be viewed by many others for years to come. Feb 12 '19 at 3:46