1
$\begingroup$

Some textbook show that the grammar $G=(N,T,P,S)$ below belongs to context-senstive grammars:

  1. S->aSBC
  2. S->abc
  3. cB->Bc
  4. bG->bb

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.