Timeline for Do an ambiguous grammar and its corresponding unambiguous version generate the same language?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Dec 9, 2014 at 22:23 | comment | added | babou | @Raphael Yes, that is what I meant. I was trying to sketch a proof for what you said, and realized the algorithm could also modify unambiguous grammars. Now that does not mean that you are wrong to suspect it is not computable. You are probably right. | |
| Dec 9, 2014 at 22:12 | comment | added | Raphael | If I'm not missing something, you just outlined how to prove by reduction (E) why disambiguating is uncomputable. If it was, you could apply the method and check if the grammar changed; the original was ambiguous iff the output is different. (Oh yes, there's a gap: what if unambiguous grammars change, too? The method may not have to "realize" whether the input is ambiguous, it may just change things that remove ambiguity, if any. Is that what you meant?) | |
| Dec 9, 2014 at 19:12 | history | edited | babou | CC BY-SA 3.0 |
more info
|
| Dec 9, 2014 at 19:00 | comment | added | babou | @Raphael Can't we have a set such that property P is undecidable for elements of S, and an equivalence relation E, such that, for every s∈S, there is a computable s'∈S such that (s,s')∈E and P(s'). What I mean is, though there is a good chance for difficulty, I am not sure your statement is so obvious. But I may have missed a point. | |
| Dec 9, 2014 at 18:24 | comment | added | babou | @Raphael I agree, though I am always wary of such statements, since though true in general, there could be families of cases where it works well ... I do not mean this specific problem, but undecidability statements in general, | |
| Dec 9, 2014 at 18:01 | vote | accept | monkey | ||
| Dec 9, 2014 at 15:19 | comment | added | Raphael | ad last paragraph: disambiguating is not computable since ambiguity is undecidable. | |
| Dec 9, 2014 at 15:15 | comment | added | babou | @monkey As I said, producing the same set of strings is the minimum you normally require. Getting "similar" parse-tree is not something that you easily get. But I do not understand what is you practical problem with ambiguity, and why you are interested in finding an unambiguous grammar D equivalent to your ambiguous one, i.e. producing the same strings. | |
| Dec 9, 2014 at 15:00 | comment | added | monkey | I mean producing the same set of strings which i intended to produce using my ambiguous version. | |
| Dec 9, 2014 at 14:53 | comment | added | babou | I am not sure I understand your question. First what is "Kkk". An unambiguous grammar D giving the same language as an ambiguous one G may be extremely different: it will produce very different parse trees, though the language is the same, where just strings are concerned. What meaning do you give to one grammar being close to another. Maybe, if you stated your purpose and "your need", I might have a better chance at giving you a proper and useful answer. | |
| Dec 9, 2014 at 14:38 | comment | added | monkey | Kkk..It means it depends how close unambiguous grammar equivalent to my ambiguous grammar i can find for my need. right? | |
| Dec 9, 2014 at 14:30 | history | answered | babou | CC BY-SA 3.0 |