2
$\begingroup$

In the context of formal grammars, is there a standard terminology to distinguish

  • words (i.e., finite sequences of letters/tokens) which only contain terminal letters/tokens, and

  • words which may contain nonterminals?

I prefer to use the term "word", unqualified, to refer to the former, because I am discussing various ways to produce words over a fixed alphabet $\Sigma$ (of terminals!), the set of nonterminals can vary from grammar to grammar, so words over them only make sense for a particular grammar. But I would still like to have a term to refer to words which may contain nonterminals: how should I best call them?

"Nonterminal words" isn't a good term because they might turn out to have only terminals; "possibly nonterminal words" or "not necessarily terminal words" is too long and syntactically awkward. "Word over $\Sigma\cup N$" is, of course, perfectly clear, but sometimes one doesn't want to introduce any symbols. What other options are available? From this related question I'm thinking maybe "symbol string" or "symbol word", but I'm not sure whether it's sufficiently distinctive. Some other possibilities are "generalized word" or perhaps "form" since the generalized words which can be derived from a grammar are called "sentential forms". Any other idea?

$\endgroup$
1
$\begingroup$

A standard term would indeed be sentential form. I think it can be used on its own, not only bound to a grammar.

It makes more sense when you know that words are also called sentences, probably harking back to the beginnings of formal grammars in the study of natural languages.

That said, there is precedence for pattern in the study of pattern languages. While they work nothing like grammars, mixed strings of alphabet symbols and variables have this name there.

$\endgroup$
  • $\begingroup$ A difference between a sentential form and a sentence is that the sentence is a special form of a sentential form, namely a sentence contains only terminals. So, could it be possible to tell apart a sentential form and sentence beyond the context of a formal grammar? $\endgroup$ – fade2black Oct 10 '17 at 18:24
  • $\begingroup$ @fade2black You can always partition an alphabet. Grammars do nothing else: sentential forms are words/sentences over $\Sigma' = \Sigma \cup N$. Not really special, unless you add the "can be derived" clause to the definition of the term. (Which I don't think we do, because then we couldn't ask, "Does G generate this sentential form?") $\endgroup$ – Raphael Oct 10 '17 at 19:26

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.