4
$\begingroup$

I do know what a "left-most-" and a "right-most derivation" is, but I stumble across the term "sentential form" and its specific differences "right-sentential form" as well as "left-sentential form" and I just don't understand what is meant with this term.

Is the concept "sentential form" so different from the concept "derivation" that it is necessary to "have" it" ?

Can some of you please explain?

Yours sincerely

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Assuming you know what leftmost and rightmost derivations are, let $S \Rightarrow^*W_1W_2\dots W_m$ be a derivation (a sequence of replacement using derivation rules), where $W_i$ is a terminal or nonterminal symbol. Then the string $W_1W_2\dots W_m$ is a sentential form of a grammar $G$. In addition, if $W_1W_2\dots W_m$ contains only terminal symbols then it is called a sentence.

If the derivation $S \Rightarrow^*W_1W_2\dots W_m$ is leftmost (rightmost) then the sentential form $W_1W_2\dots W_m$ is called left-sentential form (right-sentential form).

Is the concept "sentential form" so different from the concept "derivation"

Yes, these are different concepts. A derivation is a sequence of replacements of nonterminals using derivation rules given as a part of grammar, while a sentential form is a string over terminals and nonterminals. You generate/derive/obtain sentential form using derivation (process).

Example:

$S \rightarrow aSa \mid bSb \mid \epsilon$

Derivation: $S\Rightarrow aSa \Rightarrow abSba \Rightarrow abbSbba \Rightarrow abbbba$

Sentential form: $abbSbba$.
Sentence: $abbbba$ (since it has no nonterminal)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Hello fade2black, thanks for your answer!! Is it enough to say that "sentential form" is the mere "product" and "derivation" is the "operation / chain of operations" by which this product is obtained? Is that the relationship between those concepts? Please excuse if I am still wrong. Best wishes $\endgroup$
    – von spotz
    Commented Oct 10, 2017 at 17:56
  • $\begingroup$ A sentential form is what you obtain (kind of product as you say), and derivation is a chain of operations if by a single operation you mean a replacement of a nonterminal with the right-side of a derivation rule. I strongly recommend you the "Dragon" book pg. 167 (The first edition). The relationship between them is that a sentential form is generated/obtained as a result of derivation. $\endgroup$
    – fade2black
    Commented Oct 10, 2017 at 18:08
  • $\begingroup$ Hello Is this not the same as the element of a language, that is, a "word", already ? A "sentence" at least. $\endgroup$
    – von spotz
    Commented Oct 11, 2017 at 4:33
  • $\begingroup$ A sentential form is not an element of a language, it may contain nonterminals and hence is clearly not an element of a language. $\endgroup$
    – fade2black
    Commented Oct 11, 2017 at 4:37
  • 3
    $\begingroup$ A sentential form is any string consisting of non-terminals and/or terminals that is derived from a start symbol. Therefore every sentence is a sentential form, but only sentential forms without non-terminals are called sentences. Only sentences are in the language. $\endgroup$
    – Jochem Kuijpers
    Commented Sep 27, 2018 at 11:55

Your Answer

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

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