This was a homework assignment problem which I know I have incorrectly answered. I gave:
S -> ''
meaning that S yields the empty string. I know that the empty set and empty string are not the same. According to my professor, the answer is:
S -> S
Now, that answer seems strange to me:
I understand from a strictly mathematical standpoint, I'm not going to get anywhere with number two. However, is it required for a language to terminate? Having a language that CAN go on forever sounds okay, but one that never will terminate sounds wrong enough that I thought I'd ask if anyone knows if that's a language requirement or not.
From the Formal Grammar Wikipedia page:
the language of G, denoted as L(G), is defined as all those sentences that can be derived in a finite number of steps from the start symbol S.
Starting with S, applying the production rule once to S gives S. Applying the rule twice gives S. By induction, applying the rule any finite number still gives S. Since no sentences can be derived in a finite number of steps, the language is empty, so your professor is correct.
Alternative ways to define a grammar that accepts the empty set are L(G) = {}
(the language is empty) or P = {}
(the set of production rules is empty).