imported>Chris60308: Änderungen von 195.14.193.191 (Diskussion) auf die letzte Version von Tea2min zurückgesetzt

2021-06-16T06:26:17Z

Änderungen von 195.14.193.191 (Diskussion) auf die letzte Version von Tea2min zurückgesetzt

Neue Seite

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

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

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

== Beispiele ==
Die Grammatik
:<math>G = \left(N, T, P, S\right)</math>.
:<math>N = \{S\}</math>
:<math>T = \{a, b, c\}</math>
:<math>P : S\rightarrow aSa, S\rightarrow bSb, S\rightarrow cSc, S\rightarrow a, S\rightarrow b, S\rightarrow c, S\rightarrow \varepsilon</math>
erzeugt die Sprache aller ''a,b,c''-[[Palindrom]]e, zum Beispiel <math>abba</math> oder <math>abcacba</math>. Sie benötigt nur ein Nichtterminalsymbol, nämlich <math>S</math>.

Das Palindrom <math>abba</math> lässt sich in <math>G</math> ableiten, indem das Nichtterminalsymbol <math>S</math> zunächst zu <math>aSa</math> ersetzt wird, das darin vorhandene <math>S</math> durch <math>bSb</math>, mit dem Ergebnis <math>abSba</math>. Dieses <math>S</math> wird dadurch entfernt, dass es durch das [[Leeres Wort|leere Wort]] <math>\varepsilon</math> ersetzt wird, sodass man <math>abba</math> erhält.

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

Syntaxbäume in der [[Sprachwissenschaft|Linguistik]], die die grammatikalische Struktur eines Satzes darstellen, enthalten als Terminalsymbole die Wörter des Satzes und als Nichtterminale die grammatikalischen [[Konstituente]]n. 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.

<gallery>
Datei:Palindrome abcacba.svg|Ableitungsbaum von ''abcacba'' mit Nichtterminalsymbol ''S''
Datei:ParseTree.svg|Syntaxbaum zu {{lang|en|John hit the ball}}
</gallery>

== Literatur ==
* {{Literatur|Autor=[[John E. Hopcroft]], [[Jeffrey Ullman|Jeffry D. Ullman]]|Titel=Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie|Verlag=Addison-Wesley|Ort=Bonn|Jahr=1994|ISBN=3-89319-744-3}}

[[Kategorie:Theorie formaler Sprachen]]

Nichtterminalsymbol - Versionsgeschichte

imported>Chris60308: Änderungen von 195.14.193.191 (Diskussion) auf die letzte Version von Tea2min zurückgesetzt