1

I read formal grammar's definition from Wikipedia, and it seems like there can be such a grammar like:

S -> A

//no more rules

S and A are both non-terminals.

What language does it generates? I've thought several possibilities and rationales:

  1. An empty set, because replacing S to A doesn't generates any actual strings which only contains terminals.
  2. Any set can be an answer, because it's like solving equation S = A, to figure out what is S. Since there are no restrictions to set A, set A and set S can be anything.
  3. This is not a valid grammar because it doesn't make any sense that A, which is non terminal, doesn't have any descriptions.

Which one is right?

7
  • 2
    "The language generated by the grammar is defined to be the set of all strings without any nonterminal symbols that can be generated from the string consisting of a single start symbol by (possibly repeated) application of its rules in whatever way possible." Your grammar does not generate a language.
    – Colin Fine
    Sep 1 at 12:49
  • 2
    I’m voting to close this question because this question is not about linguistics but about computer science. Sep 1 at 12:50
  • 4
    The question is not about computer science, it's about formal language theory. This stuff is taught in syntax classes in ordinary linguistics programs and has been used explicitly for natural language theory and is therefore completely on-topic for this site. Just because some may doubt its usefulness or because it also has applications in other fields doesn't mean it has nothing to do here.
    – lemontree
    Sep 1 at 12:55
  • 4
    It's about the theory of human languages, and how to describe them.
    – user6726
    Sep 1 at 14:37
  • 2
    @lemontree We had a discussion of formal languages on meta here and I understand the tenor of that discussion as "Such questions are only on topic when a connection to the description of natural languages is made". Sep 1 at 16:59
4

To answer this, follow the definitions. From Wikipedia (see further references there):

  • The language of a grammar is the set of sentences it builds.
  • A sentence is a sentential form that contains no nonterminals.
  • A sentential form is a member of (Σ ∪ N)*.
  • Σ are terminal symbols, here ∅.
  • N are nonterminal symbols, here {S, A}.

Working our way up this list again, sentential forms are members of {S, A}*, and sentences are members of ∅*. Since ∅* = {ε} (where ε is the empty string), the language may now be either ∅ or {ε}. But ε is not generated by the language, because there is no rule that generates it.

Once you are more comfortable with this kind of questions, you can also intuitively reason that since there is no production rule that generates only terminal symbols, the generated language must be ∅. However, that does not help you to see why the grammar is valid and why your third reasoning is not correct.

If you check the definitions carefully, you see that there is no restriction that every nonterminal symbol must have corresponding rewrite rules. (However, you can show that for each grammar with such nonterminal symbols there is a smaller grammar describing the same language.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.