Construction of a counter automaton for the complement of the palindromes

Question

How would I go about constructing a nondeterministic 1-counter automaton for the language $L$ that is the complement of the palindromes $\overline{L}=\{ww^{rev}\}$ over a 2 symbol alphabet $\Sigma = \{0,1\}$?

The definition I am using for 1-NCAs consists of:

• $S$, the set of states,
• $\Sigma$, the alphabet ($\Sigma = \{0,1\}$ in our case),
• $s_{0} \in S$, the initial state,
• $F \subseteq S \times \{\text{zero},\text{nonzero}\}$, the set of accepting states, and
• $\delta : S\times\{\text{zero},\text{nonzero}\}\times A \rightarrow S \times \{-1,0,1\}$, the transition function.

Given a word $w = x_1x_2\ldots x_ny_1y_2\ldots y_n$, I know that if $x_i$ is not equal to $y_{n-i+1}$, the palindrome requirement fails. I have a feeling that the counter has something to do with that distance in between those letters but formalizing this is what I am stuck at.

Since a 1-NCA is the same thing as a NPDA (nondeterministic pushdown automaton) with only one symbol in the stack alphabet, I would accept answers using such PDAs also. This is especially since I find very few texts discussing counter automata.

Answer 1

If you know that $L$ can not be recognised by a $k$-DCA for any $k$, this gives the hint that you need to use nondeterminism to do it with 1 counter.

What we can do then is guess where the mismatch characters are, in particular, what we'll do is check that $x_{i} \neq y_{n-i+1}$ by using the counter to determine first that we're at position $i$ in the input (or rather, nondeterministically guessing that some $i$ is the right index to remember), then guessing nondeterministically that we've reached position $n-i+1$, checking that the two symbols at those positions are different, then counting down to check that we actually were at the right spot (i.e. the counter will have to be back to zero exactly when we reach the end of the input).

One version of this looks like:

So $s_{0}$ counts up until the symbol just before the one we're interested in. We nondeterministically guess to stop and record what symbol we see by moving to a different state, then $s_{1}$ and $s_{2}$ basically ignore the rest of the input until we guess we've reached the $(n-i+1)^{th}$ symbol, at which point we make sure it's different to the one at $i$, then $s_{3}$ counts down for the rest of the input. If there's no input left when the counter hits zero, we can move to $s_{4}$ and accept. If we move to $s_{4}$ too early, we can't accept because there's still input to be processed (so you could take some of the nondeterminism out by putting in an explicit sink state etc.), if we guessed to early which one was the mismatched symbol, then we can't reduce the counter to zero, so we can't get to $s_{4}$.