Sets First & Folgen prüfen für einfache Grammatik

Question

Hier ein paar Fragen, die ich auf einem Quiz in einer Klasse hatte und will einfach nur ihre Richtigkeit überprüfen. Grammatik:

S -> ABC
A -> df | epsilon
B -> f | epsilon
C -> g | epsilon

1). Die Folgen Satz von B enthält g und epsilon (T / F)? Am: F. Es gibt kein epsilon in den Folgesätzen, richtig? (Es werden nur $ aka Ende der Eingabe)

2.) Der erste Satz von S enthält d, f, g und epsilon (T / F)? Am: T. Ich sagte, falsch für das, weil ich dachte, First (S) = First (A), die g nicht ein Teil ist. Wer ist richtig?

Answer 1

1. Sie sind richtig. Wenn epsilon beteiligt ist, wird es im ersten Satz erklärt wird, nicht festgelegt die Folgen. Wenn es möglich ist, für die Herstellung des String zu Ende, dann geht $ in dem Folgesatz, nicht epsilon.
2. Das Quiz ist richtig. Die Produktion S kann in der Tat mit einer d, f beginnen, und g, und es kann auch durch die leere Zeichenkette gestartet werden. Betrachten Sie den Eingabestring g. Sie paßt S, nicht wahr? A wird durch die leere Zeichenkette erfüllt ist, wird B durch die leere Zeichenkette erfüllt, und C durch G erfüllt ist. Da A, B und C alle zufrieden sind, ist S zufrieden. Das erste Zeichen von S verbraucht ist g, so g in First (S) sein muss.