Given the following two languages : L1 = {an bn | n ≥ 1} ∪ {a} L2 = {w C wR |…

Concept: A pushdown automaton (PDA) is deterministic (a DPDA), and the language it accepts is a deterministic context-free language (DCFL), only if at every configuration (current state, next input symbol or end-of-input, and the symbol on top of the stack) there is at most one applicable move — the machine is never allowed a genuine choice, and in particular it must never need to peek further ahead than the single next symbol (or the fact that input has ended) to decide what to do. A language fails to be a DCFL only when some point in processing forces an unresolvable choice — for example, needing to know where an unmarked string's midpoint falls before reaching it.

Application — L1 = {an bn | n ≥ 1} ∪ {a}: Build a DPDA that, on reading the first 'a', pushes a stack marker and enters a state that is itself accepting (covering the string "a" alone). From that state, the next actual input symbol decides everything deterministically: another 'a' means push again and continue counting (the string is not just "a"); a 'b' means start popping one marker per 'b' read, to be matched against the count of a's; and if no further symbol ever arrives, the machine is already sitting in an accepting configuration for the singleton "a". None of these three outcomes overlaps with another, and none requires the machine to guess before the relevant symbol (or end-of-input) is actually seen — so the whole construction is deterministic, meaning L1 is a DCFL.

Application — L2 = {w C wR | w ∈ {a, b}*}: Build a DPDA that pushes each symbol of the input onto the stack for as long as it reads plain 'a's and 'b's. The moment the separating symbol C is read, the machine deterministically switches mode: for every subsequent input symbol it pops the stack top and checks that the two match, accepting exactly when the stack is empty right as the input ends. The separator C is what makes this deterministic — it is a distinct, unmistakable input symbol that triggers the mode switch, so the automaton is never required to guess where the first half of the string ends; it is told directly. So L2 is also a DCFL.

Cross-check — contrast with the unmarked case: The genuinely non-deterministic relative of L2 is the unmarked mirror-image language {w wR | w ∈ {a, b}*} with no separating symbol at all. There, a DPDA really cannot tell — without guessing — how far to push before switching to popping, because no input symbol ever signals the midpoint; that language is a classic example of a context-free language that is NOT deterministic. L2 avoids exactly this trap because of the explicit marker C, and L1's apparent ambiguity about the lone "a" similarly dissolves once each next symbol (or the absence of one) is treated as its own separate, deterministic case rather than something that must be predicted in advance.