CFL or DCFL?

Question

Is the language L = {a^nb^m
: n = m or n = m + 2} deterministic? Please anybody can clarify it.

Comments

Yes, this is Deterministic Context-Free language.

Answer 1

It is not deterministic.

A deterministic language requires that its acceptors have a determined next state on every input. Here we have ${n = m}$ or ${n = m + 2}$. Let’s say we have a deterministic acceptor that accepts the language as specified. It pushes an ${a}$ into a stack and pops whenever ${b}$ is seen in the string. Consider what happens at the last stage. Either we’ll be left with an empty stack (${n = m}$) OR we will have ${0 }$ ${b}$’s left and ${2}$ ${a}$’s to pop (${n = m + 2}$). They both should be the accepting stages, since we claimed that our acceptor works for this language. Until the end is reached, the acceptor is unable to determine which accepting state to use for a particular input. This contradicts our assumption that the acceptor was deterministic. Consequently, the language itself is non-deterministic.