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

Problem Detail: 

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

Asked By : Toralf Westström

Answered By : Patrick87

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12620