AK 1.4.2015 Aufgabe 4 First(X) ist nicht First?

Question

Würde man normalerweise das X nicht betrachten, weil es nicht First ist? Im Skript betrachtet man doch immer nur das erste Zeichen oder habe ich das missverstanden? :/

Answer 1

Aus W kann das leere Wort abgeleitet werden, so dass dann die rechte Seite mit X anfängt.

Comments

Mal angenommen das leere Wort wäre auch in First(X) und hinter X wäre noch ein weiteres NT A. Würde man dann noch mal First(A)\e zu First(S) hinzufügen?

---

Probieren Sie es aus:

    S -> Y | WXYc
    W -> ϵ | bcC | eXW
    X -> ϵ | ZY
    Y -> ϵ | d
    Z -> a

Für die obige Grammatik (ich denke so etwas hatten Sie im Sinn) bekommt man die Gleichungen

    First(S) = (First(W)\{ϵ}) ∪ (First(X)\{ϵ}) ∪ (First(Y)\{ϵ}) ∪ {c} ∪ {ϵ}
    First(W) = {e} ∪ {ϵ}
    First(X) = (First(Z)\{ϵ}) ∪ {ϵ}
    First(Y) = {d} ∪ {ϵ}
    First(Z) = {a}

und die Lösung

    First(S) = {a,c,d,e,ϵ}
    First(W) = {e,ϵ}
    First(X) = {a,ϵ}
    First(Y) = {d,ϵ}
    First(Z) = {a}