In the formal grammar context I am getting confused about the sensitive-context grammars.

For this language:


Looking for it in several sites, I found 2 different sensitive-context grammars which can generate it.

The first one is:

enter image description here

where the productions of P are:

enter image description here

The second grammar is

enter image description here

and the productions of P are:

enter image description here

Since those should be sensitive-context grammars, I understand that the first one is correct, but not sure if second one is correct too.

I mean, why those productions:

enter image description here enter image description here

... satisfy the sensitive-context grammar restriction? As I understand they dont kept the context.

Can you clarify?.

  • 2
    $\begingroup$ Tis is not a research-level question, and as such it is off-topic for this site. It may be more appropriate at cs.stackexchange.com . Having said that, the second grammar is not a context-sensitive grammar under the standard definition, but it is a noncontracting grammar, and these are known to generate only context-sensitive languages. See e.g. en.wikipedia.org/wiki/… $\endgroup$ Jun 26, 2023 at 17:11
  • $\begingroup$ cstheory.stackexchange.com/q/52991/5038 $\endgroup$
    – D.W.
    Jun 27, 2023 at 16:57


Your Answer

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

Browse other questions tagged or ask your own question.