0 Daumen
330 Aufrufe

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?

Avatar von

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?

1 Antwort

0 Daumen
 
Beste Antwort

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.

Avatar von 5,6 k

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community