0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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, 2017 at 8:04
  • $\begingroup$ ref: en.wikipedia.org/wiki/Useless_rules $\endgroup$
    – nekketsuuu
    Jan 24, 2017 at 4:11
  • $\begingroup$ ref to a similar question: "Can there be 'dead states' in a context-free grammar?" $\endgroup$
    – nekketsuuu
    Jan 24, 2017 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, 2017 at 4:25

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2017 at 3:35
  • $\begingroup$ I think an approach is the same: back to the definition. $\endgroup$
    – nekketsuuu
    Jan 22, 2017 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.