Question 46

Language $L_1 = \{0^n 1^n \mid n \ge 0\}$:

• A DPDA starts in a state where it pushes each 0 onto the stack.
• On seeing the first 1, it deterministically switches state and pops a 0 for each 1.
• If the input and stack empty simultaneously, the string is accepted.
• Every move is uniquely determined by the current state, input symbol, and top of the stack.
• Thus, $L_1$ is accepted by a DPDA, so $L_1$ is a DCFL.

Language $L_2 = \{w c w^r \mid w \in \{0, 1\}^*\}$:

• The distinct symbol $c$ serves as an explicit center marker separating $w$ and $w^r$.
• A DPDA pushes symbols of $w$ onto the stack until it reads $c$.
• Upon seeing $c$, it switches deterministically to a popping state and verifies that each subsequent symbol matches the stack top.
• No non-deterministic choice is required.
• Thus, $L_2$ is accepted by a DPDA, so $L_2$ is a DCFL.

Language $L_3 = \{w w^r \mid w \in \{0, 1\}^*\}$:

• Without a center marker, an automaton cannot determine where $w$ ends and $w^r$ begins without non-deterministically guessing the midpoint of the string.
• It is a standard result in formal language theory that $w w^r$ is a non-deterministic Context-Free Language but NOT a Deterministic Context-Free Language (DCFL).

Therefore, only $L_1$ and $L_2$ are deterministic Context-free languages (option C).