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.

  • 2
    $\begingroup$ intuitively think the concept likely translates. however CFGs are also CSGs. so you probably want to exclude CFGs. $\endgroup$ – vzn Jun 17 '14 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.