Grammatiken

(Notizen)

• Syntax: Menge von Regeln
• Produktionsregeln: Regeln, die zu bestimmten Wörtern führen
• Syntaktische Variable Term: die syntaktische Variable wird durch den Term ersetzt, der Term kann wieder eine syntaktische Variable enthalten
• Ableitung (Produktion): eine Möglichkeit, durch Anwendung der Regeln zu einem Wort zu kommen, also eine Folge von Regelanwendungen
• Startvariable: eine der syntaktischen Variablen, die als Startvariable festgelegt sein muss
• Terminale: Symbole, die zum Alphabet gehören (und damit im Wort sichtbar sind)
• Nichtterminale: syntaktischen Variablen (die im Prozess der Ableitung durch Terminale ersetzt werden)
• Zusammenfassung von Regeln: Regeln, auf deren linken Seite dasselbe Nichtterminal steht, können mit Hilfe des Symbols | (‚entweder oder’) zusammengefasst werden
• Ableitungsbaum: stellt die Folge der Regelanwendung dar

_{Quelle: Klett, Informatik 5}

In einer kleinen Stadt gibt es die zwei U-Bahnlinien U1 und U2 sowie die drei S-Bahnlinien S1, S2 und S3. Aus welchen Wörtern besteht also die formale Sprache VB (VB soll der Bezeichner für diese Verkehrslinien sein)?

1. <linie> <U-Bahn>|<S-Bahn>