snippetMinor
Do an ambiguous grammar and its corresponding unambiguous version generate the same language?
Viewed 0 times
sametheversionunambiguousambiguouslanguageitsgenerategrammarand
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#34059, answer score: 6
Revisions (0)
No revisions yet.