Grammatik Flashcards
Wie und durch welches Zeichen ist ein Alphabet definiert?
∑ – Sigma
Eine nicht leere endliche (geordnete) Menge von Symbolen.
Wie ist ein Wort definiert?
Eine Reihenfolge von endlich vielen Symbolen eines Alphabets, auch wenn es nicht den Regeln der Sprache entspricht.
Durch welches Zeichen wird ein leeres Wort dargestellt?
ɛ – Epsilon
Wie wird die Menge aller Wörter in einem Alphabet bezeichnet?
∑*
Wie ist eine (formale) Sprache definiert?
Es ist eine bestimmte Teilmenge der Menge aller möglichen Wörter ∑* über ∑.
Wie kann man Missverständnisse und Zweideutigkeiten einer Sprache verhindern?
Durch die Verwendung einer formalen Sprache.
Wie kommt eine formale Sprache zustande?
Man definiert eine Menge von Zeichenketten über einem Alphabet als zulässig.
Was stellt die Regeln zur Bildung zulässiger Zeichenketten dar?
Syntax
Wie bezeichnet man die Bedeutung eines Wortes?
Semantik
Wie nennt man die eindeutige Festlegung einer formalen Sprache mit Regeln?
Grammatik
Wie ist eine Grammatik aufgebaut?
Durch ein 4-Tupel: – N, die Menge der Nichtterminalsymbole – T, die Menge der Terminalsymbole – S ∈ N, das Startsymbol – P, die Menge der Produktionen
Wie gibt man eine Menge an Optionen an?
Durch “{ … }”
Welche Arten von Sprachen/Grammatiken gibt es?
– reguläre
– kontextfreie
– kontextsensitive
Wann ist eine Grammatik regulär?
Wenn sich ein zu bildendes nur in eine Richtung entwickelt, nach links oder rechts.
Und wenn auf der jeweiligen Seite höchstens ein Nichtterminal- hinter höchstens einem Terminalsymbol in der Produktion steht.
Wie unterscheidet sich die regulären Grammatiken noch?
Durch rechtsregulär und linksregulär.
Rechtsregulär bedeutet, dass sich ein zu bildendes Wort nach rechts entwickelt.
Linksregulär bedeutet, dass sich ein zu bildendes Wort nach links entwickelt.
Wann ist eine Sprache/Grammatik kontextfrei?
A → α
Wenn aus der Grammatik hervorgeht, dass ein Nichtterminalsymbol (=A) zu einer nichtleere Symbolfolge aus Terminal- und/oder Nichtterminalsymbolen (=α) ersetzt werden kann.
Es kommt nicht auf den Kontext / die Umgebung von dem zu ersetzenden Nichterminalsymbol an.
Wann ist eine Sprache/Grammatik (kontext-)sensitiv?
γAβ → γαβ
Wenn aus der Grammatik hervorgeht, dass ein Nichtterminalsymbol (=A) nur dann ersetzt werden kann, wenn es zwischen zwei Symbolfolgen (=γ und β) steht, d. h. im Kontext von zwei Symbolfolgen steht.
Wann ist eine Ableitung einer kontextfreien Grammatik eine Links- oder Rechtsableitung?
Rechtsableitung: Wenn immer das am weitesten rechts stehende Nichtterminalsymbol ersetzt wird
Linksableitung: Wenn immer das am weitesten links stehende Nichtterminalsymbol ersetzt wird
Wovon werden kontextfreie Sprachen akzeptiert?
Von Kellerautomaten
Wann ist eine kontextfreie Grammatik eindeutig?
Wenn für jedes Wort der Sprache nur eine Linksableitung oder Rechtsableitung gibt, sonst mehrdeutig
Was ist das besondere an kontextsensitive Sprachen?
Es können Programmiersprachen definiert und Übersetzer/Compiler konstruiert werden
