1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Which textbooks? $\endgroup$ – Yuval Filmus Nov 2 '18 at 6:37
  • $\begingroup$ "An Introduction to Formal Languages and Automata", Peter Linz $\endgroup$ – Ayumu Kasugano Nov 2 '18 at 6:41
2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Feb 12 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.