Übungsaufgaben: formale und reguläre Sprachen

Inhaltsverzeichnis Verbergen
Aufgabe 1
Aufgabe 2
Aufgabe 3
Aufgabe 4
Aufgabe 5
Aufgabe 6
Aufgabe 7
Aufgabe 8
Aufgabe 9
Aufgabe 10
Aufgabe 11
Aufgabe 12
Aufgabe 13

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
  1. Entwerfen Sie ein (sinnvolles) Syntaxdiagramm für mögliche Ersetzungsregeln dieser Grammatik. Stellen Sie diese Ersetzungsregeln auch als Menge dar.
  2. Leiten Sie einige Worte dieser Sprache ab.
  3. 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.

Schlagwörter: