<p>Usually,ambiguity of grammar is defined for constext-free languages and grammars,sometime it is extended to indexed languages and grammar,but the extension of definition of the definition is same except that the grammar and language are indexed one.</p>

<p>Now,let's try to extend the definition to context-sensitive grammar and language.One definition of context-sensitive grammar is as following:</p>

<p>The production or rewriting rule is in the form:
$$\alpha A \beta \rightarrow \alpha  \gamma \beta$$
where $\alpha , \gamma, \beta $ are string over terminal or non-terminal symbols,$A$ is non-terminal symbol.</p>

<p>Parsing every sentence of CSL by CSG ,we can get a tree or directed graph,the leaves or the final vertex are the terminal symbol,and the root is the $S$ symbol,the nodes or non-final vertex are non-terminal symbol.In this way,every sentence corresponds to one or more trees or directed graphs.</p>

<p>Now,the question: is this definition consistent with the one of CFG and CFL? If not,any suggestion for modification to make them consist to CFG or CFL?</p>

<p>If they are consist,now  the definition of ambiguity of CSG is:if a sentence of a CSL having been parsed by CSG corresponds to more than one trees or graphs  which are not isomorphic to each other(with labels),the CSG is ambiguous.</p>

<p>In this way,is there any context-sensitive language  that is inherently ambiguous?That is every CSG of the  language is ambiguous.</p>

CC BY-SA 3.0
2014-06-17T15:06:47.327Z
intuitively think the concept likely translates. however CFGs are also CSGs. so you probably want to exclude CFGs.
vzn
CC BY-SA 4.0
2021-02-11T12:14:32.790Z
https://mathoverflow.net/questions/172739/inherent-ambiguity-of-the-context-sensitive-language-l-aibicidjejfj-b Emil Jeřábek has answered a related question which show ambiguity of cfg can not extended to csg.
XL _At_Here_There
<fl.formal-languages>
Can the definition of ambiguity of CFG be extended to CSG?
XL _At_Here_There
# Can the definition of ambiguity of CFG be extended to CSG?

(Asked by: username_0 on 2014-06-17)

Usually,ambiguity of grammar is defined for constext-free languages and grammars,sometime it is extended to indexed languages and grammar,but the extension of definition of the definition is same except that the grammar and language are indexed one.

Now,let's try to extend the definition to context-sensitive grammar and language.One definition of context-sensitive grammar is as following:

The production or rewriting rule is in the form:
$$\alpha A \beta \rightarrow \alpha \gamma \beta$$
where $\alpha , \gamma, \beta $ are string over terminal or non-terminal symbols,$A$ is non-terminal symbol.

Parsing every sentence of CSL by CSG ,we can get a tree or directed graph,the leaves or the final vertex are the terminal symbol,and the root is the $S$ symbol,the nodes or non-final vertex are non-terminal symbol.In this way,every sentence corresponds to one or more trees or directed graphs.

Now,the question: is this definition consistent with the one of CFG and CFL? If not,any suggestion for modification to make them consist to CFG or CFL?

If they are consist,now the definition of ambiguity of CSG is:if a sentence of a CSL having been parsed by CSG corresponds to more than one trees or graphs which are not isomorphic to each other(with labels),the CSG is ambiguous.

In this way,is there any context-sensitive language that is inherently ambiguous?That is every CSG of the language is ambiguous.

**Tags:** fl.formal-languages
> **Comments:**
> **username_1**: intuitively think the concept likely translates. however CFGs are also CSGs. so you probably want to exclude CFGs.  
> **username_0**: https://mathoverflow.net/questions/172739/inherent-ambiguity-of-the-context-sensitive-language-l-aibicidjejfj-b Emil Jeřábek has answered a related question which show ambiguity of cfg can not extended to csg.  

---

## 0 answers

