5
$\begingroup$

I have the following formal grammar: $$G= (\{S,A,B\},\{a,b\},R,S)$$ $$R=\{S \rightarrow A\ |B, A \rightarrow \varepsilon\ | aA\ |bA, B \rightarrow \varepsilon\ |Bb\ | b\}$$

Now, we see, the production rules $A \rightarrow \varepsilon$ and $B \rightarrow \varepsilon$ implies that this grammar is not context-sensitiv ($CSG$). But on the other hand, we see this grammar satisfies the conditions for a context-free ($CFG$) grammar, because every production rule has just one NON-terminal on the left side.

We know, according to the Chomsky hierarchy, a contest-free grammar imples a contest-sensitive grammar: $CFG \implies CSG$

Now i am confused, is my grammar context-free or it is not, even if it satisfies the conditions? Can it be $CFG$ without being $CSG$?

Improve this question
$\endgroup$
1
  • $\begingroup$ A good example of a question that looks silly, unless carefully read. Questionning is a non obvious game. But it is useful. $\endgroup$
    – babou
    Commented Jun 16, 2013 at 13:48

1 Answer 1

Reset to default
2
$\begingroup$

Context-free languages are context-sensitive languages; therefore, if there's a valid CFG for a language, then there is a valid CSG for the same language. Depending on how you define CFGs and CSGs, it's possible that a CFG may not count as a CSG. It's quite often the case that CSGs aren't CFGs, even if the CSG generates a context-free language. Basically, even if CFG does not imply CSG, it is still true that CFL implies CSL. That's the confusion: the Chomsky hierarchy implies things about languages.

If your definition of a CSG says "No ϵ transitions", you're right. If it says "The only ϵ transition can be S→ϵ , then you are right. If it doesn't say something specifically excluding α→ϵ , then you're wrong. It's a matter of how you define what consistutes a valid CSG, which sounds obvious, and in fact is.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Trivial as it may be, the question intrigued me. I checked with Wikipedia. that states "the Chomsky hierarchy [...] is a containment hierarchy of classes of formal grammars". So, either Wikipedia is stating things poorly, or the definition of CS grammar has been changed, or the definition of CF grammar has changed, or the original paper (which I do not have) was careless. It is possible that it is the definition of CF that changed as some constraints on the rules limit the structuring power of parse trees with little benefit. $\endgroup$
    – babou
    Commented Jun 12, 2013 at 17:30
  • $\begingroup$ @babou Interesting. It's of course possible that I've been mistaken all along. That said, it seems certain that there exists a set of of grammar formalisms such that a regular grammar is a context-free grammar is a context-sensitive grammar, so the Chomsky hierarchy may well have been envisioned as a containment hierarchy of grammars. I suppose the take-away is that the important thing is that CFLs are CSLs, so if there is a valid CFG, there must be some valid CSG, even if your CFG isn't a valid CSG. $\endgroup$
    – Patrick87
    Commented Jun 12, 2013 at 17:56
  • $\begingroup$ From a cursory reading of Chomsky's paper, it seems that he states informally that he is not interested in $\epsilon$-rule. But he apparently ignores the problem in his formal definitions, though his later reasonning excludes $\epsilon$-rules. He states explicitly that the hierarchy is for both grammar and language (p. 143). Most likely, the empty word was simply no concern of his, whether in the grammar or in the language. But I did not read it all. Concerns changed ... hierarchy stayed ... more or less. $\endgroup$
    – babou
    Commented Jun 12, 2013 at 18:05

Your Answer

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

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