Nichtterminalsymbol

Ein Nichtterminalsymbol (auch Nichtterminal oder Variable genannt) einer formalen Grammatik ist ein Symbol, das nicht in den endgültigen Wörtern vorkommt, die in der Grammatik erzeugt werden können. Nichtterminalsymbole kommen nur in Zwischenschritten einer Ableitung vor und werden durch das Anwenden von Regeln in der Grammatik nach und nach ersetzt, bis nur noch Terminalsymbole vorhanden sind.

Definition

Für eine formale Grammatik G = (N,T,P,S) bezeichnet N die Menge der Nichtterminalsymbole. Ihr steht die Menge der Terminalsymbole T entgegen. Die Menge P der Produktionsregeln beschreibt, wie Nichtterminalsymbole durch neue Zeichenfolgen ersetzt werden dürfen. Das Startsymbol S, von dem aus alle Wörter abgeleitet werden, ist eines der Nichtterminalsymbole: $S \in N$.

Nichtterminale werden oft als Großbuchstaben geschrieben oder, etwa bei der Backus-Naur-Form, in spitze Klammern eingeschlossen.

Rolle in kontextsensitiven und kontextfreien Grammatiken

In den untersten drei Grammatiken der Chomsky-Hierarchie, den regulären, kontextfreien und kontextsensitiven Grammatiken, wird durch Anwendung einer Regel immer genau ein Nichtterminalsymbol durch eine Zeichenfolge aus Nichtterminal- und Terminalsymbolen ersetzt.

In kontextfreien und regulären Grammatiken (jede reguläre Grammatik ist kontextfrei) wird ein Nichtterminalsymbol durch höchstens ein neues Nichtterminalsymbol ersetzt. Als Konsequenz lässt sich die Ableitung eines Wortes in der Grammatik durch einen Ableitungsbaum darstellen, in dem die inneren Knoten aus Nichtterminalsymbolen bestehen und die Blattknoten aus Terminalsymbolen bestehen.

Beispiele

Die Grammatik

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

N = {S}

T = {a,b,c}

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

erzeugt die Sprache aller a,b,c-Palindrome, zum Beispiel abba oder abcacba. Sie benötigt nur ein Nichtterminalsymbol, nämlich S.

Das Palindrom abba lässt sich in G ableiten, indem das Nichtterminalsymbol S zunächst zu aSa ersetzt wird, das darin vorhandene S durch bSb, mit dem Ergebnis abSba. Dieses S wird dadurch entfernt, dass es durch das leere Wort ε ersetzt wird, sodass man abba erhält.

Ein Ableitungsbaum für das Palindrom abcacba enthält die Terminalsymbole a,b,c in den Blättern und S als Wurzel und innere Knoten.

Syntaxbäume in der Linguistik, die die grammatikalische Struktur eines Satzes darstellen, enthalten als Terminalsymbole die Wörter des Satzes und als Nichtterminale die grammatikalischen Konstituenten. Ein Satz besteht häufig aus einer Nominalphrase und einer Verbalphrase. Verbalphrasen können wiederum beispielsweise aus einem Verb und einer weiteren Nominalphrase bestehen. Nominalphrasen können zum Beispiel Nomen mit oder ohne vorangestelltem Artikel sein. Satz, Nominalphrase, Verbalphrase, Verb, Nomen und Artikel sind hier die Nichtterminalsymbole.

• 

  Ableitungsbaum von abcacba mit Nichtterminalsymbol S

• 

  Syntaxbaum zu John hit the ball

Literatur

• John E. Hopcroft, Jeffry D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Addison Wesley, Bonn 1994, ISBN 3-89319-744-3.