A definition for terminals and non-terminals of a CFG says that

terminals: The symbols that do not appear at the LHS of productions.


Are all non-terminals of the CFG given by the LHS of productions?


Given the definition you appear to be using, yes. There are only two types of symbols in a CFG, so this definition provides a dichotomy. This implicit defintion of CFGs, where the productions are provided and the terminals and non-terminals are inferred from the productions, is common in programming language circles (or at least well known), where the practical form of the grammar is the interesting aspect.

Note that this is not the only way to define a CFG, the more typical formal way gives explicit sets of terminals and non-terminals, and expresses the rules as a finite relation from the non-terminals to the set of finite strings over the non-terminals and terminals. So in this there is no "left-hand-side" as such, as being on the left entirely depends on the notation you would use to represent the productions. Moreover there's no specification that all terminals or non-terminals need to be used.

  • $\begingroup$ This is wrong. Correct answer is the one by @HendrikJan. $\endgroup$
    – vonbrand
    Jan 4 '16 at 2:19
  • $\begingroup$ @vonbrand, it's not wrong, the "non-terminals are the things on the left" implicit definition is quite widely used, especially in programming language circles. I don't like that definition, but it definitely exists. The formal, explicit version I mention second is my personal preference (a la Hendrik Jan's answer), but I'm guessing the OPs prof. is not from a theory background, and prefers the implicit define-the-CFG-by-writing-the-productions approach. $\endgroup$ Jan 4 '16 at 4:40
  • $\begingroup$ That is just a convention to don't have to write the grammar out in full, just give the productions. Check the formal definition in any automata theory and formal languages text. $\endgroup$
    – vonbrand
    Jan 4 '16 at 9:59
  • $\begingroup$ But how is that formal definition any better? I've always disliked it. You very rarely want to discuss grammars with nonterminals that have no productions. $\endgroup$ Jan 4 '16 at 11:05
  • $\begingroup$ @reinierpost In theoretical constructions the formal definition is more convenient. E.g., when going from PDA to CFG one defines non-terminals of the form $[p,A,q]$ without having to worry whether they all will have productions. $\endgroup$ Jan 6 '16 at 20:59

No. Not all non-terminals necessarily appear at the LHS of productions, that is, not every non-terminal must have productions for it.

Of course, such non-terminals are rather useless and can be removed from the grammar without changing the language. Also the dual is actually possible: there might be terminal symbols that do not appear at the RHS of productions. For example $a^*$ is a context-free language over the alphabet $\{a,b\}$.

  • $\begingroup$ The correctness of this answer depends upon using a particular definition of CFGs, there are, for better or worse, definitions that implicitly define the sets of terminals and non-terminals simply by whether hey appear on the LHS of a production or not. $\endgroup$ Jan 4 '16 at 5:01
  • 2
    $\begingroup$ @LukeMathieson Well, I am happy with the definition on wikipedia. And of course I know there are implicit definitions, written by sloppy scientists :) but I thought it was more fun to blatantly contradict your answer to set people thinking. $\endgroup$ Jan 4 '16 at 9:23
  • $\begingroup$ Hehe, now that's a motivation I can support. $\endgroup$ Jan 5 '16 at 2:47

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.