# Inherent ambiguity of the context-sensitive language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j}$ or $a^nb^nc^nd^ne^nf^n$

What is the definition of ambiguity of context-sensitive grammar?This is relevant to the definition of inherent ambiguity of context-sensitive language.And any proof for the inherent ambiguity of the language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j}$ or $a^nb^nc^nd^ne^nf^n$?

Since another question about inherent ambiguity of the context-sensitive language leads to suspicion of definition of ambiguity of CSG and inherent ambiguity of the context-sensitive language,and has been closed and deleted,a thesis founded on web claims Inherent ambiguity of the context-sensitive language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j}$ or $a^nb^nc^nd^ne^nf^n$.Here comes the two questions above.

• I personally don't know of a good definition of a parse for a context-sensitive grammar, and it seems you need that if you want to define ambiguity as having multiple parses (is there another way to define ambiguity?). It might be interesting to look at less powerful grammars (e.g. conjunctive grammars) with a clear definition of a parse. – Max Jun 26 '14 at 20:23

Let me define a context-sensitive language strongly unambiguous if it is recognizable by a context-sensitive grammar such that every string in the language has a unique derivation. (Note that in the CFL world, this condition is much stronger than plain unambiguity.)

I don’t know if there is a sensible well-behaved definition of an unambiguous context-sensitive language, but any reasonable such definition should have at least the property that every strongly unambiguous language is unambiguous. (The definition in Noah S’s answer violates this condition, so I do not consider it reasonable: it may well happen that a derivable string has no leftmost derivation at all, even if it has a unique derivation; for much the same reason, that definition also apparently violates another reasonable requirement, namely that the class of unambiguous CSL should be invariant under left-to-right reversal.)

As explained below in more detail, it follows that under any reasonable definition, the language given in the question is unambiguous. Furthermore, it is impossible to unconditionally prove that any context-sensitive language is inherently ambiguous without serious assumptions from computational complexity.

The class of context-sensitive languages is well-known to coincide with $\mathrm{NSPACE}(O(n))$, i.e., languages recognizable by a nondeterministic linear-space Turing machine. This contains the class of deterministic linear-space languages $\mathrm{DSPACE}(O(n))$. There is a natural notion of unambiguity used in this context (e.g., classes like UL or UP): a nondeterministic Turing machine is unambiguous if every string is accepted by at most one computation path. The class $\mathrm{USPACE}(O(n))$ of languages recognized by an unambiguous linear-space Turing machine is intermediate between the other two, that is, $$\mathrm{DSPACE}(O(n))\subseteq\mathrm{USPACE}(O(n))\subseteq\mathrm{NSPACE}(O(n))=\mathrm{CSL}.$$ To put things into context, the closure of any of these classes under polynomial-time reductions is $\mathrm{PSPACE}$.

Now, the point is that the reduction of $\mathrm{NSPACE}(O(n))$ to CSL preserves the number of accepting paths: that is, given a nondeterministic linear-space Turing machine $M$, one can construct a context-sensitive grammar $G$ recognizing the same language in such a way that every $G$-derivation of a string $w$ corresponds to a unique accepting path of $M$ on input $w$, and vice versa. In particular, if $M$ is unambiguous, then $G$ is strongly unambiguous. So, the class of strongly unambiguous CSL languages (and a fortiori, unambiguous CSL languages under any reasonable definition) contains $\mathrm{USPACE}(O(n))$, and therefore $\mathrm{DSPACE}(O(n))$.

The language in the question can be recognized in a straightforward way by a deterministic logarithmic-space Turing machine, hence it is strongly unambiguous.

Moreover, the existence of any inherently ambiguous CSL language would imply a separation of $\mathrm{USPACE}(O(n))$ and $\mathrm{DSPACE}(O(n))$ from $\mathrm{NSPACE}(O(n))$, and by padding, also a separation of (U)L from NL. These are notoriously difficult open problem in complexity, akin to separation of P from NP.

Incidentally, since every CFL (or LOGCFL) language can be recognized in deterministic space $O((\log n)^2)$ (and quasi-polynomial time), this also shows that every context-free language is a strongly unambiguous context-sensitive language. Given that one might reasonably demand the opposite, this suggests that there is in fact no reasonable definition of unambiguous CSL.

• Yes,"Moreover, the existence of any inherently ambiguous CSL language would imply a separation of USPACE(O(n)) and DSPACE(O(n)) from NSPACE(O(n)), and by padding, also a separation of (U)L from NL",This is why I try to give a definition and find a proof of existence of inherently ambiguous CSL.And I had thought that it has been found before reading your answer.By some clue,it seems that DSPACE(O(n)) is not equivalent to NSPACE(O(n)) – XL _At_Here_There Jun 27 '14 at 14:21
• Hmm. A couple of comments: first, I seriously doubt that expressing it in terms of grammars may help resolving the DSPACE vs. NSPACE problem. CS grammars do not have the nice structural properties of CF grammars; they are essentially slightly obfuscated Turing machines, and their properties are generally easier to understand when expressed directly using Turing machines. In any case, one cannot separate NSPACE(O(n)) from DSPACE(O(n)) using a simplistic language based on counting occurrences of symbols, Boolean operations, and similar, as in your question. Such languages are invariably easy ... – Emil Jeřábek supports Monica Jun 27 '14 at 15:09
• ... to recognize by a low-space deterministic TM. I don't know if there are any natural candidates for the separation, apart from things like a “universal nondeterministic linear-space language”. Second, while NSPACE(O(n)) is widely expected to be different from DSPACE(O(n)), I wouldn't be so sure whether it is different from USPACE(O(n)). For one thing, using the Immerman–Szelepcsényi inductive counting, one can for any NSPACE(O(n)) Turing machine $M$ give another NSPACE(O(n)) TM that computes a specific unique computation path (say, the lexicographically first) of $M$ for any accepted ... – Emil Jeřábek supports Monica Jun 27 '14 at 15:14
• ... input string. This does not imply NSPACE(O(n))=USPACE(O(n)) as such (because the machine computing the unique path will itself have more than one path), but it makes the possibility somewhat plausible. – Emil Jeřábek supports Monica Jun 27 '14 at 15:17
• @EmilJeřábek, that's a really good point that I wasn't aware of - that issue honestly didn't occur to me. – Noah Schweber Jun 27 '14 at 16:33

EDIT: Emil points out serious issues in the notion of unambiguity I give below, to the point that it's clear this notion isn't appropriate. (OP, I think you should un-select this answer and select Emil's answer.)

Only a partial answer: I'm no expert in this area, but it seems that the definition of ambiguity can be extended in a natural way to arbitrary context-sensitive grammars.

Note: I believe - although correct me if I'm wrong - that the thesis the OP refers to is that of Saichaitanya Jampana (https://shareok.org/bitstream/handle/11244/8173/Jampana_okstate_0664M_1373.pdf?sequence=1); and the specific part referenced is page 17.

Quick overview of the basics: A general formal grammar is a tuple $(N, \Sigma, P, S)$ with $N$ and $\Sigma$ disjoint finite sets (nonterminal and terminal symbols respectively), $P$ a finite set of production rules (i.e., expressions of the form "$p\rightarrow q$" with $p\in (\Sigma\cup N)^*N(\Sigma\cup N)^*$ and $q\in (\Sigma\cup N)^*$), and $S\in N$ a fixed symbol; the language $L(G)$ attached to a grammar $G$ is the set of strings in $(\Sigma\cup N)^*$ which can be derived from $S$ using finitely many applications of rules in $P$. Iff $p$ appears as the left hand of some rule in $P$, say $p$ is convertible. Now, a context-free grammar is just a grammar satisfying a special condition: that whenever $"p\rightarrow q$"$\in P$, we have that $p$ is a single symbol from $N$.

The wikipedia page - and most references I could find - on ambiguity then defines ambiguity only for context-free grammars: a context-free grammar $G$ is unambiguous if every $p\in L(G)$ has a unique leftmost derivation (that is, a sequence of applications of rules in $P$ to the starting symbol $S$, concluding with $p$, such that at each stage the leftmost nonterminal symbol is converted). Since in arbitrary formal grammars, derivation rules need not be applied to only individual nonterminal symbols, this definition doesn't carry over meaningfully.

However, it seems that it can be easily generalized: for an arbitrary formal language $L(G)$ and $p\in L(G)$, a leftmost derivation of $p$ in $G$ is a derivation of $p$ in which at each stage, a rule from $P$ is applied to the leftmost convertible substring. So, e.g., if (with $x, y, z, w\in N$) $P$ contains the rules $xy\rightarrow yz, z\rightarrow wy, yw\rightarrow x, wy\rightarrow z$, then $$xy\mapsto yz\mapsto ywy\mapsto yz$$ is not a leftmost derivation of $yz$, since the leftmost convertible substring of the penultimate string is $yw$, not $wy$.

Note that this notion of ambiguity extends that for context-free grammars, since the convertible strings in a context-free grammar are all individual nonterminal symbols.

Finally, note that this notion of ambiguity (just like the standard one) applies to grammars, not languages. For a language $L$, the relevant notion is "inherent ambiguity": $L$ is inherently ambiguous (within a certain context of languages, e.g. context-sensitive) if it is not generated by any non-ambiguous grammar (again within that context).

Of coure, I'm not sure this is the actual definition, but I strongly suspect this is what S. Jampana means. Regardless, the notion of inherent ambiguity explained above is that used by Jampana: see page 17.

And, of course, I don't have off the top of my head a proof of why the languages he mentions are in fact inherently ambiguous, so this isn't a complete answer, even if I do have the right notion of ambiguity.

• OP, please let me know if the thesis I mention is not the one you are referring to. – Noah Schweber Jun 26 '14 at 21:31
• ,Yes,the thesis I mention is the one you are referring to.And his supervisor has given me some reference,but Due to other reason,I can not find the reference. – XL _At_Here_There Jun 26 '14 at 23:17
• Inherent ambiguity can be defined as having multiple parsing trees or labelled directed graphs.Based on this, a unambiguous grammar can give only one trees for one word or sentence.And then we can induce the definition of unambiguous grammar by other definition.His advisor gives me reference as following,but I cann't find 1. pp. 185-211 of Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill Book Company, New York, NY, 1966. 2. pp. 233-246 of Michael A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Publishing Company, Inc., Reading, MA, 1978. – XL _At_Here_There Jun 26 '14 at 23:29
• @XL_at_China, WorldCat says there are copies of both of those books in the National Library of China; perhaps that is accessible to you? – Max Jun 27 '14 at 8:45
• @NoahS: I believe you are reading way too much into the off-hand (and most likely not well thought out) remark from the thesis. The definition you propose has multiple problems as mentioned in my answer, but most importantly, I am pretty sure that the language in the OP is unambiguous under your definition: the straightforward log-space algorithm for the language by left-to-right scan will translate to a grammar with the property that any partial derivation ends with a string containing a unique nonterminal (corresponding to the TM head) that appears in the LHS of any applicable rule. ... – Emil Jeřábek supports Monica Jun 27 '14 at 14:08