Hinweis: Im Folgenden werden das Symbol N für die nichtterminalen Zeichen und das Symbol T für die terminalen Zeichen gleichberechtigt neben den Symbolen VN und VT verwendet.
Aufgabe 1
Die folgende Grammatik beschreibt eine Formale Sprache:
G = (N,T,P,S)
N = {Satz, Prädikat, Subjekt, Objekt}
T = {DER_BAUER, DER_GÄRTNER, ER, SIE, SCHNEIDET, RASIERT, MÄHT, DIE_WIESE, DIE_HAARE, DEN_PELZ}
P = ?
S = Satz
- Entwerfen Sie ein (sinnvolles) Syntaxdiagramm für mögliche Ersetzungsregeln dieser Grammatik. Stellen Sie diese Ersetzungsregeln auch als Menge dar.
- Leiten Sie einige Worte dieser Sprache ab.
- Finden Sie einige „sinnlose“ Sätze, die jedoch syntaktisch richtig gebildet wurden. Lässt sich die Grammatik so abändern, dass ausschließlich sinnvolle Sätze entstehen?
Aufgabe 2
Gesucht ist eine Grammatik G, die eine formale Sprache über dem Alphabet X = {0,1} erzeugt, zu der alle binären Worte gerader Parität gehören. Übersetze diese Grammatik in einen DEA.
Aufgabe 3
Welche Sprache erzeugt die Grammatik G = (N,T,P,S) gegeben durch N = {S,A,B}, T = {0,1}, S = S und P = {(S -> 0A | 1B), (A -> 1 | 1S | 0AA), (B -> 0 | 0S | 1BB)}.
Aufgabe 4
Gegeben sind die beiden Grammatiken G1 und G2 mit N = {S}, T = {(,)} und P1 = {S -> () | (S) | SS} bzw. P2 = {S -> () | (S) | SSS} zur Bildung korrekter Klammerterme. Zeige dass L(G_2) \subset L(G_1) gilt.
Aufgabe 5
Welche formale Sprache wird von der Grammatik G gegeben durch N = {S}, T = {a,b}, S = S und P = {S -> a | b | aSa | bSb} erzeugt? Leite mindestens fünf Wörter her und versuche, eine charakteristische Eigenschaft aller Wörter der Sprache zu finden.
Aufgabe 6
Gib eine Grammatik G an, die die formale Sprache L(G) = \{a^{n}b^{2n} \mid n> 0\} erzeugt.
Aufgabe 7
Gib eine reguläre Grammatik für vereinfachte Bezeichner (einer Programmiersprache, z. B. Java oder Pascal) an, die nur aus dem Buchstaben a, der Ziffer 1 und dem Sonderzeichen + gebildet werden. Das Eingabealphabet sei demzufolge X = {a,1,+}. (Was könnten „a“, „1“ und „+“ repräsentieren?)
Aufgabe 8
Gib eine reguläre Grammatik für Integerzahlen, wie in Pascal bzw. Java festgelegt, an.
Aufgabe 9
Zeige, dass es zur Grammatik mit den Produktionen S -> aSb | aSa | bSa | bSb | \epsilon eine äquivalente linkslineare Grammatik gibt.
Aufgabe 10
Wie lauten Grammatik und Akzeptor der Sprache über X= {a,b}, bei der sämtliche Wörter mit a beginnen und mit b enden? Ist die Sprache regulär?
Aufgabe 11
Gegeben sei die folgende Grammatik G = (N,T,P,S) mit P = {(S -> AE), (A -> m | me), (E -> e | s | es)}. Bestimme L(G). Gib eine linkslineare Grammatik zu L an. Gib einen vollständigen Ableitungsbaum an … mes?
Interpretiere in den Worten der Sprache e als „erben“, m als „müllers“ und s als „spinnen“. Was stellst du fest?
Aufgabe 12
Gegeben sei die Grammatik G = (N,T,P,S) mit T = {a,b,c}, N = {S,A,B,C} mit dem Startsymbol S und den Produktionen P = {(S -> Sa | Ab), (A -> Ba | Cc), (B -> Cb), (C -> Aa | b)}.
- Zeige, dass das Wort bcacababa in der Sprache liegt, indem du eine geeignete Ableitung angibst.
- Konstruiere einen äquivalenten deterministischen Automaten.
- Zeige, dass alle Worte der Form bcac(aba)iba für i >= 0 auch in der Sprache liegen.
Aufgabe 13
Sei L = { an | n = 1,4,9,16, … (Quadratzahl)} = {a,aaaa,aaaaaaaaa,…}. Zeige, dass diese Sprache nicht regulär ist.