Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [ambiguity]

Questions related to (un)ambiguous formal grammars or automata, inherent ambiguity of languages, and similar topics.

Filter by
Sorted by
Tagged with
8 votes
1 answer
352 views

Converting 2-ambiguous NFA to unambiguous NFA

This must be known, but somehow I can't locate a reference about this. Let $A$ be a nondeterministic finite automaton (NFA) over words of an alphabet $\Sigma$. I say that $A$ is unambigous if, for ...
a3nm's user avatar
  • 9,409
4 votes
1 answer
102 views

Is there any context-free language that is inherently ambiguous as an indexed language

Indexed languages are defined as being produced by indexed grammar. Is there any context-free language that is inherently ambiguous as an indexed language? That is, is there a context-free language ...
WangAtChicago's user avatar
5 votes
0 answers
98 views

Useful notion of ambiguous growing context-sensitive language

As far as I understand there is no useful notion of ambiguous context-sensitive language. For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
naloa's user avatar
  • 61
3 votes
1 answer
166 views

Compressing grammars by introducing ambiguity and left-recursion

This is a reference request. What is known about the following questions? Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a new grammar $G'$ which also ...
Martin Berger's user avatar
25 votes
3 answers
15k views

How is proving a context free language to be ambiguous undecidable?

I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
Ulkmun's user avatar
  • 379