Nullbarkeit, Theoretische Informatik

Question

Frage:

Grammatik G = ({S,A,B,C,D}, {a,b,c}, R1, S) mit

R1 = {

S -> BD | AS,

A -> aC | DD,

B -> b | DBA,

C -> c | A | BS,

D -> CAB | Epsilon

}

Lösung: Nullbar: D,A,C, nicht nullbar: S,B

Wie komme ich auf die Lösung?

Comments

Wie lautet die Definition von "nullbar"?

---

Wenn ein Symbol nach Epsilon übergeht, oder?

Das wäre dann auf jeden Fall D.

Achso, dann auch A, weil man von A nach DD, also D kommt. Und C, weil man von C nach A nach D nach Epsilon kommt?

---

Wenn ein Symbol nach Epsilon übergeht, oder?

Frag nicht mich, schau in deine Unterlagen. Dort sollte die Definition stehen.

Ich nehme die Definition mal so hin.

---

Eine Variable A heißt nullbar,

falls

A =>* ε

(Laut meinen Unterlagen)

Ist meine vorherige Antwort dann richtig?

Answer 1

D ist nullbar wegen

        D ⇒ ε.

A ist nullbar wegen

        A ⇒ DD ⇒ εε = ε.

C ist nullbar wegen

        C ⇒ A ⇒ DD ⇒ εε = ε.

B ist nicht nullbar weil Wörter die aus B abgleitet werden mindestens ein b enthalten.

S ist nicht nullbar weil Wörter die aus S abgleitet werden nur über B abgeleitet werden können.

Comments

Hi,

ich solle nun eine äquivalente Grammatik G1' ohne ε-Regeln angeben (außer ggfs. S ->ε).

Die Lösung lautet: G1' = ({S,A,B,C,D}, {a,b,c}, R1', S) mit

R1' = {

S -> BD | AS | B | S,

A -> aC | DD | a | D,

B -> b | DBA | BA | DB | B,

C -> c | A | BS,

D -> CAB | AB | CB | B

}

Wie gehe ich hier vor, um auf die neuen Einträge für R1' zu kommen?

Laut Skript sind ε-Regeln eliminierbar. Zu jeder cf-Grammatik existiert eine äquivalente cf-Grammatik G' ohne ε-Regeln und nullare Variablen, falls ε ∉ L(G) und mit der einzigen ε-Regel S-> ε nd der einzigen nullbaren Variablen S, falls ε ∈ L(G) und S das Startsymbol ist.