Prime e segui Imposta verificare la presenza di semplice grammatica

Question

Ecco un paio di domande che avevo su un quiz in una classe e vogliono solo verificare la loro correttezza. Grammatica:

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

1.) Il set di B Segui contiene ge epsilon (T / F)? Ans: F. Non c'è epsilon nei set Seguire, giusto? (Solo $ aka fine dell'input)

2.) La prima serie di S contiene d, f, g, e epsilon (T / F)? Ans: T. Ho detto false per questo perché ho pensato First (S) = First (A), che g non è una parte di. Chi ha ragione?

Answer 1

1. Lei ha ragione. Se Epsilon è coinvolto, che sarà contabilizzata nel primo set, non il Seguire set. Se è possibile per la produzione alla fine della stringa, allora $ va nel set Seguire, non Epsilon.
2. Il quiz è corretta. La produzione S può infatti iniziare con qualsiasi di d, f, eg, e può anche essere iniziato dalla stringa vuota. Si consideri la stringa di input g. Si abbina S, giusto? A è soddisfatto dalla stringa vuota, B è soddisfatta dalla stringa vuota, e C è soddisfatta da g. Poiché A, B, e C sono tutte soddisfatte, S è soddisfatto. Il primo carattere è consumata da S g, quindi g deve essere in primo luogo (S).