Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

A grammar that accepts the empty set by the rule S->S

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:

  1. It will never terminate.
  2. It isn't so much a language as the absence of one.

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.

like image 705
Levi Morrison Avatar asked Sep 26 '11 17:09

Levi Morrison


People also ask

What is the language generated by the CFG S -> ASB S -> AAB?

A language generated by a CFG is a context-free language (CFL).

Can context-free grammar be empty?

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.

What are the rules of context-free grammar?

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.

What is context-free grammar with example?

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.


1 Answers

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).

like image 98
Mark Byers Avatar answered Nov 12 '22 04:11

Mark Byers