The question is pretty short, but I've been thinking about it quite some time: Are terminal symbols that are not in the defined alphabet still valid?

  • $\begingroup$ Not a real answer here, so I write a comment. If you define a grammar $G = (N, \{a, b\}, P, S)$ and have a production rule like $\alpha \to \beta c \gamma$, one may say that this rule cannot be in $P$. But all in all the question is not really profound. Why should anyone define a grammar with such inconsistency? $\endgroup$ – ttnick Jun 8 '18 at 14:06
  • $\begingroup$ @PHPNick because it's not mine :) $\endgroup$ – just_deko Jun 8 '18 at 15:06

No. The grammar is defined like this:

G = (V,SIGMA, R, S) where V is your set of variables (non-terminals) and SIGMA is your alphabet (terminals). All the symbols you are allowed to use in the substitution of a rule are the union of V and SIGMA. If you simply cannot use a symbol out of that set, since it does not exists in the context of your grammar.

  • $\begingroup$ So if I have a production rule S -> a where S is a variable in the grammar but a isn't anywhere, than what chomsky type is the grammar? Non-existant? $\endgroup$ – just_deko Jun 8 '18 at 12:51
  • $\begingroup$ Yes. It is not a valid grammar $\endgroup$ – Samuel Yvon Jun 8 '18 at 12:55

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.