2
$\begingroup$

A language $L$ is deterministic context-free if and only if there is a deterministic push-down automaton M such that $L = L(M)$.

According to the answer key of this quiz, the above statement is false. Which is odd to me, if a context free language is one that can be defined by a pushdown automata, would a deterministic context free language not also be defined by a deterministic pushdown automata? Perhaps it's the "if and only if" that is at issue here.

I'm also referencing information from this post Are there inherently ambiguous and deterministic context-free languages?, which does imply that the above statement should be true.

$\endgroup$
1
$\begingroup$

I would agree with you, but local definitions may differ.

One point might be the definition of $L(M)$. What is the acceptance type of the PDA? That might be "empty stack" or "final state". For deterministic PDA the two modes of acceptance are not equivalent. But also here wikipedia agrees that $L$ indicates final state, which is commonly used for DCFL.

$\endgroup$

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.