Nonterminal symbol

A non-terminal symbol (also non-terminal , Nonterminalsymbol or variable called) a formal grammar is a symbol that is not in the final words occur, which can be generated in the grammar. Non-terminal symbols only occur in intermediate steps of a derivation and are gradually replaced by applying rules in the grammar until only terminal symbols are left.

definition

For a formal grammar, denotes the set of nonterminal symbols. It is opposed to the multitude of terminal symbols. The set of production rules describes how non-terminal symbols can be replaced by new strings. The start symbol can be derived from which all words, one of the non-terminal symbols: . ${\displaystyle G=(N,T,P,S)}$ ${\displaystyle N}$ ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle S\in N}$

Non-terminals are often written as capital letters or, for example in the Backus-Naur form , enclosed in angle brackets.

Examples

The grammar

${\displaystyle G=\left(N,T,P,S\right)}$.

${\displaystyle N=\{S\}}$

${\displaystyle T=\{a,b,c\}}$

${\displaystyle P:S\rightarrow aSa,S\rightarrow bSb,S\rightarrow cSc,S\rightarrow a,S\rightarrow b,S\rightarrow c,S\rightarrow \varepsilon }$

generates the language of all a, b, c - palindromes , for example or . It only needs one non-terminal symbol, namely . ${\displaystyle abba}$ ${\displaystyle abcacba}$ ${\displaystyle S}$

The palindrome can be derived in that the nonterminal symbol is first replaced with, the existing symbol with , with the result . This is removed by replacing it with the empty word so that one obtains. ${\displaystyle abba}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle aSa}$ ${\displaystyle S}$ ${\displaystyle bSb}$ ${\displaystyle abSba}$ ${\displaystyle S}$ ${\displaystyle \varepsilon }$ ${\displaystyle abba}$

A derivation tree for the palindrome contains the terminal symbols in the leaves and as roots and inner nodes. ${\displaystyle abcacba}$ ${\displaystyle a,b,c}$ ${\displaystyle S}$

Syntax trees in linguistics , which represent the grammatical structure of a sentence, contain the words of the sentence as terminal symbols and the grammatical constituents as nonterminals . A sentence often consists of a noun phrase and a verb phrase . Verb phrases can in turn consist of a verb and another noun phrase, for example. Noun phrases can, for example, be nouns with or without a preceding article. Sentence , noun phrase , verb phrase , verb , noun and item are the non-terminal symbols here.

• 

  Derivation tree from abcacba with non-terminal symbol S

• 

  Syntax tree for John hit the ball

literature

• John E. Hopcroft , Jeffry D. Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . Addison-Wesley, Bonn 1994, ISBN 3-89319-744-3 .