Theoretische Informatik (Vorlesung 11)

Aufgabe 1

Sei Σ = {0,1} ein Alphabet und L = { w ∈ Σ, w ist ein palindrom}.
Geben Sie eine Grammatik für L an.

S → 0S0 | 1S1 | 0 | 1 | Σ

Von welchem Typ ist die Grammatik?
→ Kontextfrei, (Nur Regeln der Form A → l
mit A ∈ N und l ∈ (N ∪ Σ)*)
→ nicht Kontextsensitiv (Nur Regeln der Form u1Au2 → u1wu2
mit A ∈ N, w ∈ (N ∪ Σ)* und |w| >= 1
oder S → ε, dann darf S auf keiner rechten Regelseite vorkommen.)
denn S → ε ∈ P und z.B. S → 1S1 ∈ P,
S kommt also auf der rechten Seite einer Produktion vor.

Einschub:
Konstruiere aus der kontextfreien Grammatik für L eine Grammatik, die sowohl kontextfrei als auch kontextsensitiv ist:

1) Führe ein neues Nichtterminalsymbol S‘ ein.
2) Ersetze in jeder Regel A → l mit l = ε S durch S‘.
3) Führe die neue Regel S → S‘ ein
4) Führe neue Regeln wie folgt ein:
In jeder Regel der Form A → l‘ durch streichen beliebug vieler S‘.

Ursprungsgrammatik:
S → 0S0
S → 1S1
S → 0
S → 1

neue Grammatik:
S‘ → 0S’0
S‘ → 00
S‘ → 1S’1
S‘ → 11
S‘ → 0
S‘ → 1
S → S‘
S → ε

Tipp: Anschauen für die Klausur!

• L = { w ∈ Σ*, w Palindrom und w ≠ ε}
• L = { w ∈ Σ*, w Palindrom und w ist gerade / ist ungerade}
• L = { w ∈ Σ*, w ist ungerades Palindrom mit 1 in der Mitte}

Ende_Einschub

Aufgabe 2

Konstruieren Sie einen DEA für die Menge L = {w ∈ {0,1}*; w hat Präfix 01}.
Entwickeln Sie hieraus, wie in der Vorlesung, eine  rechtslineare Grammatik G
mit L(G) = L.

Automat:

A = { Q={q0,q1,q2,q3}, Σ={0,1}, q0, d, F={q2} }
G = (N, Σ, S, P} soll rechtslineare Grammatik
mit L(G) = L, N = Q, Σ = Σ, S = q0,
P = { q0 → 0=q1, q0  → 1=q3, q1 → 0=q3, q1 → 1=q2, q2 → 0=q2, q2 → 1=q2,
q3 → 0=q3, q3 → 1=q3, q2 → ε}

Aufgabe 3

S → 0B | 1A
A → 0 | 0s | 1AA
B → 1 | 1S | 0BB

a) Welche Wörter sind in G aus 0S1ABS in einem Schritt ableitbar?

10 Wörter:

0S1ABS → 00B1ABS
0S1ABS → 01A1ABS
0S1ABS → 0S10BS
0S1ABS → 0S10sBS
0S1ABS → 0S11AABS
0S1ABS → 0S1A1S
0S1ABS → 0S1A1SS
0S1ABS → 0S1A0BBS
0S1ABS → 0S1AB0B
0S1ABS → 0S1AB1A

b) Ist 0S1ABS aus S in G ableitbar?

Nein. Um ein Wort l ∈ (N ∪ Σ*) mit l1 = 0 ableiten zu können, muss am Anfang die Regel S → 0B genutzt werden.
Es gibt keine Regel der Form B → S…, d.h. kein Wort der Form 0S… kann in G abgeleitet werden.

c) Zeigen Sie, dass das Wort 10101 nicht in G ableitbar ist.

1. An erster Stelle steht eine 1: Nutzung der Regel S → 1A    =1A
2. An zweiter Stelle steht eine 0: Nutzung der Regel A → 0S   =10S
3. An dritter Stelle steht eine 1: Nutzung der Regel S → 1A     =101A
4. An vierter Stelle steht eine 0: Nutzung der Regel A → 0S     =1010S
5. An fünfter Stelle steht eine 1: Nutzung der Regel S → 1A     =10101A

Da für alle Regeln A → l in G gilt | l | >= 1,
d.h. für ein Wort w mit 10101A -> w gilt |w| > 5

d) Zeigen Sie, dass für alle w ∈ (N ∪ Σ)* mit S |-* w gilt:
w enthält die Zeichen 0 und A genauso oft wie die Zeichen 1 und B.
( |w|0 + |w|A = |w|1 + |w|B)

Beweis per Induktion über die Anzahl n der Ableitungen

Induktionsanfang: Gelte n=1. Also gilt: S|-(1) w  [w ist in einem Schritt aus S ableitbar] , d.h. w=0B oder w=1A. In beiden Fällen gilt:
|w|0 + |w|A = |w|1 + |w|B

Induktionsschritt: (n → n+1). Es gelte die Behauptung für n.
zu zeigen:  Die Behauptung gilt auch für n+1.

Sei w ∈ (N ∪ Σ)* mit S|-(n+1) w. [w ist in n+1 Schritten aus S ableitbar].
Sei w ∈ (N ∪ Σ)* mit S|-(n) w‘ |-(1) w.
Laut Induktionsvoraussetzung gilt |w’|0 + |w’|A = |w’|1 + |w’|B.

w entsteht aus w‘ durch das Anwenden einer Regel aus G.

Fallunterscheidung nach den Regeln

1. Fall: w entsteht aus w‘ durch anwenden der Regel S→0B:
|w|0 + |w|A = 1 + |w’|0 + |w’|A = 1 + |w’|1 + |w’|B = |w|0 + |w|B