# Is a regular grammar valid if it only contains production rules that have nonterminals in the right operand?

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.

• – nekketsuuu Jan 24 '17 at 4:11
• ref to a similar question: "Can there be 'dead states' in a context-free grammar?" – nekketsuuu Jan 24 '17 at 4:11
• @nekketsuuu Thank you for this reference. I was not aware of those important concepts of proper CFGs and unproductive rules. – 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.

• 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) ? – yoyo_fun Jan 22 '17 at 3:35
• I think an approach is the same: back to the definition. – nekketsuuu Jan 22 '17 at 5:07