Наборы First & Follow проверяют простоту грамматики

Question

Вот несколько вопросов, которые у меня возникли во время викторины в классе, и я просто хочу проверить их правильность.Грамматика:

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

1.) Следующий набор B содержит g и epsilon (T / F)?Ans:F.В следующих наборах нет эпсилона, верно?(Только $ aka конец ввода)

2.) Первый набор S содержит d, f, g и эпсилон (T / F)?Ans:T.Я сказал false для этого, потому что я думал, что First (S) = First (A) , частью которого g не является.Кто прав?

Answer 1

<Ол>

Вы правильны. Если эпсилон участвует, это будет учтено в первом наборе, а не последующая набор. Если это возможно для производства до конца строки, а затем $ идет в комплекте Follow, не эпсилон.

Тест правильно. Производство S действительно может начинаться с любым из D, F, и G, а также может быть запущена пустой строкой. Рассмотрим входную строку г. Это соответствует S, не так ли? А удовлетворяются пустой строкой, В удовлетворяются пустой строкой, и С удовлетворяются г. Так как А, В, и С, все удовлетворены, S выполнен. Первый символ, потребляемая S есть г, поэтому г должно быть на первом (S).