Is every sentential form also a right-sentential form?

99 Views Asked by At

Ullman's Introduction to Automata, Languages and Computing (1979) says

10.6 LR(0) GRAMMARS

...

A right-sentential form is a sentential form that can be derived by a rightmost derivation.

Is every sentential form also a right-sentential form, by definition? (I guess so.) In Chapter 4 Context Free Grammars, I learned that

  • Given a CFG, a sentential form is a string of terminals and nonterminals which can be derivable from the start symbol.

    Since a sentential form is derivable from the start symbol, there exists at least one parse tree from the start symbol and the sentential form.

  • If w is in L(G) for CFG G, then w has at least one parse tree, and corresponding to a particular parse tree, w has a unique leftmost and a unique rightmost derivation.

    I think the same can be generalized from a string of terminals to a sentential form.

So isn't it that each sentential form always has at least one rightmost derivation? Therefore, isn't every sentential form also a right-sentential form, by definition? Why is the concept of "right sentential form" introduced?

Thanks.

1

There are 1 best solutions below

2
On

$$\begin{align}S&\to A B\\ A&\to a\\ B&\to b\\ \end{align} $$ For this grammar, $aB$ is not a right sentential form because $A$ was not the rightmost non-terminal when it was replaced. So $aB$ cannot appear in any rightmost derivation even though it can be derived.