views:

796

answers:

1

Here's a few questions I had on a quiz in a class and just want to verify their correctness. Grammar:

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

1.) The Follow set of B contains g and epsilon (T/F)? Ans: F. There is no epsilon in the Follow sets, correct? (Only $ aka end of input)

2.) The First set of S contains d, f, g, and epsilon (T/F)? Ans: T. I said false for this because I thought First(S) = First(A), which g is not a part of. Who is correct?

+2  A: 
  1. You are correct. If epsilon is involved, it will be accounted for in the First set, not the Follow set. If it's possible for the production to end the string, then $ goes in the Follow set, not epsilon.
  2. The quiz is correct. The production S can indeed start with any of d, f, and g, and it can also be started by the empty string. Consider the input string g. It matches S, right? A is satisfied by the empty string, B is satisfied by the empty string, and C is satisfied by g. Since A, B, and C are all satisfied, S is satisfied. The first character consumed by S is g, so g must be in First(S).
Rob Kennedy