Sei `A_1=(Q_1, Sigma, delta_1, I_1, F_1)` ein endlicher Automat mit `L_1 = L(A_1)` und `A_2=(Q_2, Sigma, delta_2, I_2, F_2)` ein endlicher Automat mit `L_2 = L(A_2)`. Ohne Beschränkung der Allgemeinheit gilt `Q_1 nn Q_2 = O/`.
Konstruieren Sie einen endlichen Automaten `A`, für den gilt: `L(A) = L_1 @ L_2`!
Konstruieren Sie zu jedem der folgenden NEA einen äquivalenten DEA und zeichnen Sie die zugehörigen Transitionsdiagramme!
a) `({p,q,r,s}, {0,1}, delta_1, p, {s})`
| `delta_1` | `0` | `1` |
| `p` | `p,q` | `p` |
| `q` | `r` | `r` |
| `r` | `s` | - |
| `s` | `s` | `s` |
Lösung
b) `({p,q,r,s}, {0,1}, delta_2, p, {q, s})`
| `delta_2` | `0` | `1` |
| `p` | `q,s` | `q` |
| `q` | `r` | `q,r` |
| `r` | `s` | `p` |
| `s` | `-` | `p` |
Lösung
Geben Sie deterministische endliche Automaten an, die folgende Sprachen über dem Alphabet `Sigma = {0,1}` akzeptieren:
a) Die Menge aller Zeichenketten mit drei aufeinanderfolgenden Nullen.
b) Die Menge aller Zeichenketten, in denen jeder Block von fünf aufeinanderfolgenden Zeichen zumindest zwei Einsen enthält.
c) Die Menge aller Zeichenketten deren drittletztes Zeichen eine Null ist.
Ist die Sprache der Palindrome über dem Alphabet `Sigma = {a,b}` (Zeichenketten, die vorwärts und rückwärts gelesen das Selbe ergeben) regulär?
Hinweis: Verwenden Sie das Pumping-Lemma sowie eine konkrete Zeichenkette bestehend aus "vielen" a, einem b und "vielen" a, welche ein Palindrom ist.
Gegeben sei ein endlicher Automat `A`. Beschreiben Sie seine Sprache durch einen regulären Ausdruck! Zeichnen Sie das zugehörige Transitionsdiagramm!
a) `A = ({p,q,r},{a,b},delta_1,p,{r})`
| `delta_1` | `a` | `b` |
| `p` | `q` | `-` |
| `q` | `-` | `r` |
| `r` | `q` | `- ` |
Lösung
b) `A = ({p,q},{0,1},delta_2,p,{q})`
| `delta_2` | `0` | `1` |
| `p` | `p` | `q` |
| `q` | `p` | `q` |
Lösung
Beschreiben Sie verbal die von den folgenden regulären Ausdrücken bezeichneten Mengen:
a) `(11+0)^"*"(00+1)^"*"`
b) `(1+01+001)^"*"(epsilon+0+00)
Konstruieren Sie endliche Automaten, die zu den folgenden regulären Ausdrücken äquivalent sind:
a) `ab+(b+aa)b^"*"a`
b) `ab(((ba)^"*"+bbb)^"*"+a)^"*"b`
Geben Sie kontextfrei Grammatiken an, die folgende Mengen erzeugen:
a) Die Menge der Palindrome über dem Alphabet `Sigma = {0,1}` (Zeichenketten, die vorwärts und rückwärts gelesen das Selbe ergeben).
Lösung
b) Die Menge aller korrekten Klammerausdrücke über dem Alphabet `Sigma = {(,)}` (jede öffnende Klammer hat eine entsprechende schließende Klammer und Paare zusammengehörendnder Klammern sind richtig eingebettet - eine solche Zeichenkette besitzt kein Präfix mit mehr schließenden Klammern als öffnenden Klammern).
Lösung
c) Die Menge aller Zeichenketten mit doppelt so vielen Einsen wie Nullen.
Lösung
d) Die Menge aller Zeichenketten über dem Alphabet `Sigma = {a,b}`, die nicht von der Form `ww^R` für eine beliebige Zeichenkette `w` sind (`w^R` steht für `w` von hinten gelesen).
Lösung
Sei `G` eine Grammatik mit den angegebenen Produktionen:
S -> aB | bA
A -> a | aS | bAA
B -> b | bS | aBB
Geben Sie einen Ableitungsbaum für die Zeichenkette aaabbabbba, eine Rechtsableitung und eine Linksableitung an.
Eine Sprache besteht nur aus endlich vielen Strings. Geben Sie eine kontextfreie Grammatik für diese Sprache an. Ist es möglich eine äquivalente reguläre Menge anzugeben?
Gegeben sei die Grammatik `G = (N,T,P,X)" mit "T={a,b}, N={A,X}" und "P={A->a, A->Aa, X->Xb, X->Ab}`. Welche Sprache wird beschrieben? Können Sie einen endlichen Automaten für diese Sprache angeben - wenn ja, wie sieht dieser aus?
Gibt es eine kontextfreie Grammatik `G` über dem Alphabet `{a,b}`, so dass `L(G)` gerade `x in T^"*"` enthält, für die `|x|` durch 3 teilbar ist? Falls ja, geben Sie eine entsprechende Grammatik an! Handelt es sich dabei sogar um eine reguläre Sprache? Falls ja, geben Sie einen regulären Ausdruck und einen endlichen Automaten an!
Für `T={a,b}` und `N={A,B,X}` suche man wenistens zwei kontextfreie Grammatiken `G=(N,T,P,S)`, so dass `L(G)={w in T^"*" | w" enthält gleich viele a wie b "}.
Gegeben sie die Menge `L = { ba^nb | n >= 0} uu {a^nba | n > 0}`.
a) Ist dies eine reguläre Menge?
b) Falls nein, begründen Sie dies, andernfalls geben Sie einen regulären Ausdruck und einen zugehörigen endlichen Automaten an.
Geben Sie die Sprache eines endlichen Automaten durch eine regulären Ausdruck an und zeichnen Sie ein Übergangsdiagramm, wenn dieser jedes Anfangsstück der Zeichenkette 100100100100... akzeptiert.
Die Ackermann-Funktion sei definiert durch:
`{:(ack(0,y),=,y+1),(ack(x+1,0),=,ack(x,1)),(ack(x+1,y+1),=,ack(x,ack(x+1,y))):}`
a) Geben Sie in geschlossenen Formeln (d.h. ohne Rekursion direkt berechenbar) folgende Funktionen `f_0, f_1, f_2` und `f_3` an, die durch `f_i(y)=ack(i,y)`, definiert sind. Es sollen dabei nur noch die Grundrechenarten sowie die Exponentialfunktion vorkommen. ("ack" bezeichnet die Ackermann-Funktion.)
b) Gelingt eine ähnliche Darstellung auch für `f_4`?
c) Berechnen Sie - soweit möglich - `f_4(0)=ack(4,0), f_4(1)=ack(4,1), f_4(2)=ack(4,2)` und `f_4(3)=ack(4,3)`!
Gegeben sei die Grammatik `G= (N,T,P,X)" mit "T={a,b}, N={A,X}" und "P={X->XX|ab}`.
a) Bestimmen Sie die Sprache der Grammatik `G`.
b) Von welchem Typ ist sie?
c) Gibt es dazu eine Äquivalente von Typ 3?
Anm. d. Autors: Diese Aufgabe ist die Selbe wie Aufgabe 11. Doch soll dieser Platz nicht ungenutzt bleiben.
Die Aufgabe zum Kellerautomaten haben wir nicht behandelt. Ich kann deswegen keine Lösung zur Verfügung stellen, will sie aber trotzdem aufführen:
Konstruieren Sie einen Kellerautomaten, der `{ww^R | w` aus `(0+1)^"*"}` mit leerem Keller akzeptiert.
Hinweis: Beachten Sie, dass eine Eingabe genau dann abgelehnt wird, wenn es keinen Weg gibt, der zu einem leeren Keller führt. Das bedeutet in diesem Beispiel, dass nach jeder verarbeiteten Teilzeichenkette die Mitte erreicht sein könnte und der Automat versuchen könnte mit den folgenden Zeichen den Keller zu löschen. Ist die Zeichenkette von der Form `ww^R`, so "rät" der Automat einmal richtig und leert auf diesem Weg den Keller (Achtung, der gesuchte Kellerautomat ist also nicht deterministisch). Ist die Zeichenkette nicht von dieser Form, so wird der Keller auf keinem der eingeschlagenen Wege geleert.
Gegeben sei die Grammatik `G= (N,T,P,X)` mit `T={a,b,c}`, `N={B,C,X}` und `P={C->c,B->b,CB->BC,X->aBC,X->aXBC}`.
a) Bestimmen Sie die Sprache der Grammatik G.
b) Von welchem Typ ist sie?
c) Gibt es dazu eine Äquivalente vom Typ 3?