1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – user3767495 Jan 2 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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