For example:

S -> Sa

Let's say the alphabet is {a} and that is the ONLY production rule of the grammar. Is that grammar valid regular grammar ? Or valid grammar at all? Can it be a context free grammar, but not a regular one ?

As far as I can think... a grammar tree built on it will never end, it will never have only leaves so there is NO string that is accepted or generated by this grammar so it should not be considered a valid grammar.

However I did not see in the definition of grammar this specific constraint of a grammar, that it necessarily should have a production rule with ONLY terminal symbols on the right hand side of a production rule.

  • $\begingroup$ Hi yoyo_fun. Do you know about accepting an answer? If your question is resolved, please click the green checkmark of a better answer. If not, make a comment about it in order to tell readers more about the problem (if you want). I also ask you to accept answers of your other questions (if they are satisfactory). Of course, not accepting all answers is OK since accepting is not mandatory. Regards, $\endgroup$ – nekketsuuu Jan 22 '17 at 8:04
  • $\begingroup$ ref: en.wikipedia.org/wiki/Useless_rules $\endgroup$ – nekketsuuu Jan 24 '17 at 4:11
  • $\begingroup$ ref to a similar question: "Can there be 'dead states' in a context-free grammar?" $\endgroup$ – nekketsuuu Jan 24 '17 at 4:11
  • $\begingroup$ @nekketsuuu Thank you for this reference. I was not aware of those important concepts of proper CFGs and unproductive rules. $\endgroup$ – yoyo_fun Jan 24 '17 at 4:25

Back to the definition. According to Wikipedia, a context-free grammar $G$ is a 4-tuple $(V, \Sigma, R, S)$. In this case, $G = (V, \Sigma, R, S)$ can be defined as

  • $V$, nonterminals, is $\{S\}$,
  • $\Sigma$, terminals, is $\{a\}$,
  • $R$, production rules, is $\{ S \mapsto Sa \}$, and
  • $S$ is the start symbol and an element of $V$.

So this is a context-free grammar although the language recognized by $G$ is empty as you noticed.

You can also verify whether this is a regular CFG by going back to the definition.

  • $\begingroup$ So it is both a regular grammar and a context free grammar but it accepts no string. It is like a Deterministic Finite State Machine which has no Finite State ??? Or it has Finite State but no transition to it right? Is that kind of machine still a Finite State Machine (FSM) ? $\endgroup$ – yoyo_fun Jan 22 '17 at 3:35
  • $\begingroup$ I think an approach is the same: back to the definition. $\endgroup$ – nekketsuuu Jan 22 '17 at 5:07

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.