# Is this formal grammar context-free (CFG) but not context-sensitive (CSG)?

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$?

• A good example of a question that looks silly, unless carefully read. Questionning is a non obvious game. But it is useful. Jun 16, 2013 at 13:48

• 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. Jun 12, 2013 at 18:05