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.