5
$\begingroup$

If I have an ambiguous grammar G and its disambiguated version D. Then which one is true L(D) ⊂ L(G) , L(G) ⊂ L(D) or L(G)=L(D)?

As I tried with some examples to transform a grammar to it unambiguous version but i found that both are equivalent.

I mean is there a specific set relation between both. Please help me and provide an example if possible.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The semantics of "its X-version" give the answer. $\endgroup$
    – Raphael
    Commented Dec 9, 2014 at 15:18

1 Answer 1

Reset to default
6
$\begingroup$

When you disambiguate a grammar, you usually want at least to keep the language the same. So the answer is that you want $\mathcal L(G)=\mathcal L(D)$.

If you accepted that $\mathcal L(G)\subset \mathcal L(D)$ then you could simply choose $\mathcal L(D)=\Sigma^*$, since $\Sigma^*$ has an unambiguous grammar. Of course $\Sigma$ is the terminal alphabet.

If you accepted that $\mathcal L(D)\subset \mathcal L(G)$ then you could simply choose $\mathcal L(D)=\emptyset$ since $\emptyset$ has an unambiguous grammar.

I assume you were considering context-free (CF) languages. You should have said so.

And you should remember some facts that will not help:

  • Some CF languages are inherently ambiguous, so that you cannot find an unambiguous grammar for them. Furthermore, it is undecidable whether a CF language is inherently ambiguous,

  • It is undecidable to know whether a grammar is ambiguous, hence it is not clear when a disambiguating transformation is needed.

See also wikipedia page on ambiguous grammars.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Kkk..It means it depends how close unambiguous grammar equivalent to my ambiguous grammar i can find for my need. right? $\endgroup$
    – monkey
    Commented Dec 9, 2014 at 14:38
  • $\begingroup$ 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. $\endgroup$
    – babou
    Commented Dec 9, 2014 at 14:53
  • $\begingroup$ I mean producing the same set of strings which i intended to produce using my ambiguous version. $\endgroup$
    – monkey
    Commented Dec 9, 2014 at 15:00
  • $\begingroup$ @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. $\endgroup$
    – babou
    Commented Dec 9, 2014 at 15:15
  • $\begingroup$ ad last paragraph: disambiguating is not computable since ambiguity is undecidable. $\endgroup$
    – Raphael
    Commented Dec 9, 2014 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.