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?

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

2 Answers 2

Reset to default
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?

Improve this answer
$\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$.

Improve this answer
$\endgroup$
1
  • $\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$
    – John L.
    Feb 12, 2019 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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