I know that DCFL are unambiguous languages and DCFL languages have one-to-one correspondence with LR grammars.
But I wanted to know if there can be an instance that deterministic context free grammar is ambiguous.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
No, there is no deterministic context-free grammar that is ambiguous since any deterministic context free grammar (DCFG) must be unambiguous.
Here is definition 2.47 of the book introduction to the theory of computation, third edition, by Michael Sipser.
A deterministic context-free grammar is a context-free grammar such that every valid string has a forced handle.
Furthermore, here is definition 2.62.
An LR($k$) grammar is a context-free grammar such that the handle of every valid string is forced by lookahead $k$.
A DCFG is the same as an LR(0) grammar. All LR($k$) grammars are unambiguous, by definition.
-
$\begingroup$ Ohhh. that's the reason why.Thank you also for mentioning good reference. I am also weak at decidability problems.Can you suggest a resource for practice? $\endgroup$ Jan 2, 2019 at 12:41
$\begingroup$
$\endgroup$
6
I was also struggling with this problem. I think I might have found an ambiguous DCFG G = ({S,T,A},{a,u,v},R,S), where R is defined as
S -> ATa | aTa
T -> uv
A -> a
G is ambiguous because there are two different leftmost derivations for string auva.
S => ATa => aTa => auva
S => aTa => auva
However, G is also a DCFG because there is only one leftmost reduction
auva >-> Auva >-> ATa >-> S
which means that there are a total of three valid strings: auva, Auva, ATa. And we can show that each of them has a forced handle by enumerating all possibilities.
-
$\begingroup$ This is a left-most reduction, because there is no non-terminal to the left of the reduced non-terminal: $auva \rightarrowtail aTa \rightarrowtail S$. It corresponds to your second rightmost derivation. So $A\to a$ is not a forced handle; $T\to uv$ is also possible. An ambiguous grammar cannot be deterministic; intuitively, the ambiguity means that there are at least two possible choices and at some point the parser must encounter one of them. See Sipser for a more formal proof. $\endgroup$– riciNov 20, 2021 at 3:54
-
$\begingroup$ I'm not sure if my understanding of leftmost reduction is correct. On page 136, Sipser wrote: in a leftmost reduction, each reducing string is reduced only after all other reducing strings that lie entirely to its left. So I guess auva >-> aTa is not a valid leftmost reduction step because a lies entirely to the left of uv? $\endgroup$– legoerNov 20, 2021 at 8:35
-
$\begingroup$ A reducing string is a string which is replaced in some reduce step. (p. 135). It is not a string which just happens to appear on the right-hand side of a production. Of course, it does have to appear on the right-hand side of a production, but that's not sufficient to make it a reducing string. To be a reducing string it must actually be reduced in some step in the reduction. So $a$ is not a reducing string in $auva \rightarrowtail aTa \rightarrowtail S$, and $auva \rightarrowtail aTa$ is most certainly a leftmost reduction step. $\endgroup$– riciNov 20, 2021 at 15:24
-
$\begingroup$ I think I might have understood why I was wrong. When we want to tell if a reduction is a leftmost reduction, we can't use a stepwise definition like that in leftmost derivation (i.e., every step unfolds the leftmost non-terminal in the previous step). Instead, we should examine the whole reduction and check if after one reduction step (say the resulting non-terminal is X), any string lies entirely on the left of X is reduced in some later step. Am I correct? $\endgroup$– legoerNov 20, 2021 at 15:42
-
$\begingroup$ There is a stepwise constraint: the end of each reduce step is no earlier than the symbol inserted by the previous reduce step. That's proven in Sipser, too, iirc. $\endgroup$– riciNov 20, 2021 at 15:47