<p>In the formal grammar context I am getting confused about the <strong>sensitive-context grammars</strong>.</p>
<p>For this language:</p>
<p><img src="https://chart.googleapis.com/chart?cht=tx&amp;chl=%20L=%7B%5C%7Ba%5En,b%5En,c%5En%20%7C%20n%20%5Cgeq%201%5C%7D" alt="foo+bar" /></p>
<p>Looking for it in several sites, I found 2 different <strong>sensitive-context grammars</strong> which can generate it.</p>
<p><strong>The first one is</strong>:</p>
<p><a href="https://i.sstatic.net/Js0v6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Js0v6.png" alt="enter image description here" /></a></p>
<p>where the productions of P are:</p>
<p><a href="https://i.sstatic.net/7906J.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/7906J.png" alt="enter image description here" /></a></p>
<p><strong>The second grammar is</strong></p>
<p><a href="https://i.sstatic.net/vf0tF.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vf0tF.png" alt="enter image description here" /></a></p>
<p>and the productions of P are:</p>
<p><a href="https://i.sstatic.net/fSq0b.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fSq0b.png" alt="enter image description here" /></a></p>
<p>Since those should be <strong>sensitive-context grammars</strong>, I understand that the first one is correct, but <strong>not sure if second one is correct too</strong>.</p>
<p>I mean, why those productions:</p>
<p><a href="https://i.sstatic.net/SVbSc.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SVbSc.png" alt="enter image description here" /></a>
<a href="https://i.sstatic.net/PRTlY.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/PRTlY.png" alt="enter image description here" /></a></p>
<p>... satisfy the <strong>sensitive-context grammar</strong> restriction? As I understand they dont kept the context.</p>
<p>Can you clarify?.</p>

CC BY-SA 4.0
2023-06-26T17:11:40.897Z
Tis is not a research-level question, and as such it is off-topic for this site. It may be more appropriate at https://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. https://en.wikipedia.org/wiki/Context-sensitive_grammar#Formal_definition
Emil Jeřábek
CC BY-SA 4.0
2023-06-27T16:57:50.870Z
https://cstheory.stackexchange.com/q/52991/5038
D.W.
<grammars>
Grammal formal doubt. Context-sensitive grammar
user69507
# Grammal formal doubt. Context-sensitive grammar

(Asked by: username_0 on 2023-06-26)

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

For this language:

![foo+bar](https://chart.googleapis.com/chart?cht=tx&chl=%20L=%7B%5C%7Ba%5En,b%5En,c%5En%20%7C%20n%20%5Cgeq%201%5C%7D)

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](https://i.sstatic.net/Js0v6.png)](https://i.sstatic.net/Js0v6.png)

where the productions of P are:

[![enter image description here](https://i.sstatic.net/7906J.png)](https://i.sstatic.net/7906J.png)

**The second grammar is**

[![enter image description here](https://i.sstatic.net/vf0tF.png)](https://i.sstatic.net/vf0tF.png)

and the productions of P are:

[![enter image description here](https://i.sstatic.net/fSq0b.png)](https://i.sstatic.net/fSq0b.png)

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](https://i.sstatic.net/SVbSc.png)](https://i.sstatic.net/SVbSc.png)
[![enter image description here](https://i.sstatic.net/PRTlY.png)](https://i.sstatic.net/PRTlY.png)

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

Can you clarify?.

**Tags:** grammars

> **Comments:**
> **username_1**: Tis is not a research-level question, and as such it is off-topic for this site. It may be more appropriate at https://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. https://en.wikipedia.org/wiki/Context-sensitive_grammar#Formal_definition  
> **username_2**: https://cstheory.stackexchange.com/q/52991/5038  

---

## 0 answers

