0
$\begingroup$

I am currently reading Sipser's book on the Theory of Computation, and was wondering about the the question in the title.

Here is my current understanding of the concepts:

A deterministic context free grammar is a context free grammar in which every valid string has a forced handle.

Sipser's Book on the Theory of Computation introduces the DK Test to determine whether a CFG is deterministic. We can examine the accept states of the DFA that the DK Test constructs to determine if every valid string in the grammar has a forced handle. Thus, any CFG that passes the test has to be both Unambiguous and Deterministic.

The accept states must have the following properties:

  1. Each accept state only contains 1 completed rule
  2. The accept state cannot contain any dotted rules where a terminal symbol immediately follows the dot.

It seems possible to modify some conditions in the construction of the DK Test DFA to have it identify only unambiguous CFGs. However, I wasn't successful in doing so yet. Does anyone have any ideas how I can approach this?

Improve this question
$\endgroup$

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.