If you want to make money online : Register now

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

, , No Comments
Problem Detail: 

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?

Asked By : mavavilj
Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51427

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback