|
1.1 Notation:r /
Nichtterminalsymbole werden in Backus-Naur-Form, in spitzen Klammern < >, gesetzt.
Der Pfeil ® einer Produktionsregel wird durch das Zeichen ::= dargestellt.
Alternativen werden durch einen senkrechten Strich ½ getrennt.
Geschwungene Klammern {} bedeuten Wiederholungen und eckige Klammern [] umschließen optionale Teile.
1.2 Definition Grammatik:
Eine Grammatik G=(T,N,P,S) ist ein Viertupel mit:
. T endliche Menge der terminalen Symbole
. N endliche Menge der nichtterminalen Symbole, T Ç N = Ø
. P Produktionssystem mit endlich vielen Produktionsregeln
. S 0 N, Startsymbol
1.3 Bestandteildefinition:
Terminale T: Das Alphabet der Sprache. Terminalsymbole sind Zeichen oder Wörter, die nicht mehr weiter zerlegt werden können und mit denen jeder Satz einer Sprache formuliert wird.
Tdeutsch = {a, ...z, A, ...Z, der, die , das, Professor, Studentin, ...}
T*: Menge aller Wörter, die durch die Hintereinanderreihung endlich vieler Terminalsymbole einschließlich des leeren Wortes e, erzeugt werden können
Nichtterminale N: Hilfssymbole, mit deren Hilfe die Grammatikregeln formuliert werden können. Jedes nichtterminale Symbol entspricht einer Variablen und läßt sich in eine Folge anderer nichtterminaler und terminaler Symbole umschreiben.
Ndeutsch = {, , , , ,
, , , ...}
Äquivalent zu T* wird N* definiert.
Produktionen P: enthält Regeln zur Konstruktion von Zeichenketten der Sprache und legen fest, wie ein nichtterminales Symbol weiter ersetzt werden kann. Sie werden meistens in der Notation u ® v angegeben.
Es gilt: u,v 0 (T È N)*
Damit eine solche Regel anwendbar ist, muß u mindestens ein Nichtterminalsymbol enthalten.
® .
Das bedeutet, daß ein Satz aus einem Subjekt, einem Prädikat, einem Objekt und einem Punkt an dessen Ende besteht.
Startsymbol S: Ein Startsymbol S ist ein ausgezeichnetes nichtterminales Symbol mit dem jede Anwendung von Produktionsregeln beginnt.
Beispielsweise ist für die deutsche Sprache das nichtterminale Symbol "Satz" ein Startsymbol.
1.4 Definition Formale Sprache (allgem. Sprache)
Die von der Grammatik G erzeugte formale Sprache L(G) wird definiert durch die Menge aller Wörter w, die nur aus Terminalsymbolen bestehen und die alle aus dem Startsymbol S ableitbar sind. (Übersichten zum Gesamtverständnis der Sprachen, Automaten, Grammatiken und ihrer Zusammenhänge finden sie in den Anlagen)
1.5 Definition Aufzählbare Sprachen
Eine Sprache L(G) heißt aufzählbar, wenn es einen Algorithmus gibt, der alle Wörter w dieser Sprache nacheinander erzeugen kann. Dazu gehören:
- Typ-0-Sprachen
- Sprachen die von Turingmaschinen mit eingeschränktem Eingabeband akzeptiert werden
1.6 Definition Entscheidbar Sprachen
Eine Sprache L(G) über einer Mnege von Terminalsymbolen T, L(G) Í T* , heißt entscheidbar, wenn es eien Algorithmus gibt, der nach endlich vielen Schritten feststellt, ob für jedes w Í T* gilt, daß entweder w Î L(G) oder w Ï L(G) zutrifft.
- bilden echte Teilmengen der aufzählbaren Sprachen
- sind echte Obermenge der kontextsensitiven Sprachen
- werden durch Kellerautokaten erkannt. Dies sind endliche Automaten, die um eine Keller erweitert werden, um bereits erkannte Zeichen zu speichern
|
