Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Some textbook show that the grammar $G=(N,T,P,S)$ below belongs to context-senstive grammars:
where N={S,B}, T={a,b,c}.
I am confused by the fact that the production rule cB->Bc cannot satisfy the definition of a CSG. So, why is the above grammar belongs to CSG?
Your confusion is not unexpected. That grammar is not a context-sensitive grammar in its usual strict sense.
However, that grammar can be considered as a context-sensitive grammar in some situations. The Wikipedia entry on context-sensitive grmmar reads the following.
Some definitions of a context-sensitive grammar only require that for any production rule of the form $u \to v$, the length of $u$ shall be less than or equal to the length of $v$. This seemingly weaker requirement is in fact weakly equivalent, see Noncontracting grammar#Transforming into context-sensitive grammar.
You may want to double check the definition of CFG and exposition thereafter in the textbook you mentioned.
