1
$\begingroup$

I read following here:

Unambiguous grammars do not always generate a DCFL.
Example: For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An arbitrary string of this language cannot be parsed without reading all its letters first, which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string.

Now I am confused about definition of Deterministic Context Free Language or Deterministic Context Free Grammar.

According to wikipedia, DCFG are those that can be derived from Deterministic Pushdown Automata and they generate DCFL.

I read

A CFG is deterministic iff there are no two productions with the same terminal prefix on the right side of them.

I find that this condition applies on above example grammar. But still the grammar is said to not generate DCFL. Thus, it seems that this definition wrong, because the condition "no two productions with the same terminal prefix on the right side of them" holds on above grammar and above grammar does not seem to generate DCFL. Q1. So is it indeed wrong?

DPDA is defined as pushdown automata that never has a choice in its move (for any given next input character and stack top).

It seems that above definition of DCFG is wrong because it puts all importance on input string, whereas definition of DPDA puts condition on both input character and stack top.

Q2. However then how exactly these conditions in the definition of DPDA failed for above example CFG?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.