www.wikidata.de-de.nina.az

Nichtterminalsymbol Ein auch Nichtterminal Nonterminalsymbol oder Variable genannt einer formalen Grammatik ist ein Symb

Nichtterminalsymbol

Ein Nichtterminalsymbol (auch Nichtterminal, Nonterminalsymbol 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 Bearbeiten

Für eine formale Grammatik bezeichnet die Menge der Nichtterminalsymbole. Ihr steht die Menge der Terminalsymbole entgegen. Die Menge der Produktionsregeln beschreibt, wie Nichtterminalsymbole durch neue Zeichenfolgen ersetzt werden dürfen. Das Startsymbol , von dem aus alle Wörter abgeleitet werden, ist eines der Nichtterminalsymbole: .

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

Beispiele Bearbeiten

Die Grammatik

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

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

Ein Ableitungsbaum für das Palindrom enthält die Terminalsymbole in den Blättern und 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.

Literatur Bearbeiten

  • 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Nichtterminalsymbol auch Nichtterminal Nonterminalsymbol oder Variable genannt einer formalen Grammatik ist ein Symbol das nicht in den endgultigen Wortern vorkommt die in der Grammatik erzeugt werden konnen 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 BearbeitenFur eine formale Grammatik G N T P S displaystyle G N T P S nbsp bezeichnet N displaystyle N nbsp die Menge der Nichtterminalsymbole Ihr steht die Menge der Terminalsymbole T displaystyle T nbsp entgegen Die Menge P displaystyle P nbsp der Produktionsregeln beschreibt wie Nichtterminalsymbole durch neue Zeichenfolgen ersetzt werden durfen Das Startsymbol S displaystyle S nbsp von dem aus alle Worter abgeleitet werden ist eines der Nichtterminalsymbole S N displaystyle S in N nbsp Nichtterminale werden oft als Grossbuchstaben geschrieben oder etwa bei der Backus Naur Form in spitze Klammern eingeschlossen Beispiele BearbeitenDie Grammatik G N T P S displaystyle G left N T P S right nbsp N S displaystyle N S nbsp T a b c displaystyle T a b c nbsp P S a S a S b S b S c S c S a S b S c S e displaystyle P S rightarrow aSa S rightarrow bSb S rightarrow cSc S rightarrow a S rightarrow b S rightarrow c S rightarrow varepsilon nbsp erzeugt die Sprache aller a b c Palindrome zum Beispiel a b b a displaystyle abba nbsp oder a b c a c b a displaystyle abcacba nbsp Sie benotigt nur ein Nichtterminalsymbol namlich S displaystyle S nbsp Das Palindrom a b b a displaystyle abba nbsp lasst sich in G displaystyle G nbsp ableiten indem das Nichtterminalsymbol S displaystyle S nbsp zunachst zu a S a displaystyle aSa nbsp ersetzt wird das darin vorhandene S displaystyle S nbsp durch b S b displaystyle bSb nbsp mit dem Ergebnis a b S b a displaystyle abSba nbsp Dieses S displaystyle S nbsp wird dadurch entfernt dass es durch das leere Wort e displaystyle varepsilon nbsp ersetzt wird sodass man a b b a displaystyle abba nbsp erhalt Ein Ableitungsbaum fur das Palindrom a b c a c b a displaystyle abcacba nbsp enthalt die Terminalsymbole a b c displaystyle a b c nbsp in den Blattern und S displaystyle S nbsp als Wurzel und innere Knoten Syntaxbaume in der Linguistik die die grammatikalische Struktur eines Satzes darstellen enthalten als Terminalsymbole die Worter des Satzes und als Nichtterminale die grammatikalischen Konstituenten Ein Satz besteht haufig aus einer Nominalphrase und einer Verbalphrase Verbalphrasen konnen wiederum beispielsweise aus einem Verb und einer weiteren Nominalphrase bestehen Nominalphrasen konnen zum Beispiel Nomen mit oder ohne vorangestelltem Artikel sein Satz Nominalphrase Verbalphrase Verb Nomen und Artikel sind hier die Nichtterminalsymbole nbsp Ableitungsbaum von abcacba mit Nichtterminalsymbol S nbsp Syntaxbaum zu John hit the ballLiteratur BearbeitenJohn E Hopcroft Jeffry D Ullman Einfuhrung in die Automatentheorie formale Sprachen und Komplexitatstheorie Addison Wesley Bonn 1994 ISBN 3 89319 744 3 Abgerufen von https de wikipedia org w index php title Nichtterminalsymbol amp oldid 213003403