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.
A language generated by a CFG is a context-free language (CFL).
A right-regular grammar is a context-free grammar in which the right-hand side of every production rule has one of the following forms: the empty string; a string consisting of a single non-terminal symbol; or a string consisting of a single terminal symbol followed by a single non- terminal symbol.
A formal grammar is "context-free" if its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a context-sensitive grammar.
A context free grammar (CFG) is a forma grammar which is used to generate all the possible patterns of strings in a given formal language. G is a grammar, which consists of a set of production rules. It is used to generate the strings of a language. T is the final set of terminal symbols.
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).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With