A one-counter automaton $M = (Q, S, \Gamma, t, s, A)$ is a pushdown automaton where the stack alphabet $\Gamma$ contains just two symbols $\#$ and $g$. The symbol $\#$ is initially written on the bottom of the stack and is then not erased. Apart from $\#$ the only stack symbol used is $g$ (so that, at any point, the contents of the stack, read from bottom to top, are $\#g^n$ for some value of $n > 0$). A language accepted by a one-counter automaton is called a one-counter language. Let $S = \{a,b\}$. A palindrome in $S^∗$ is a string a such that a is equal to its reversal; for example, $a, aa, aba$ and $abba$ are palindromes whereas $ab, abb$ and $abaa$ are not. Let $A$ be the set of strings in $S^*$ that are not palindromes.
(i) Show that $A$ is a one-counter language.
(ii) Construct a context-free grammar $G$ with $L(G) = A$. Hint: First show that a string $a$ is not a palindrome if and only if $a$ is of the form $\beta u\gamma v\delta$ with $\beta,\gamma,\delta\in S^*$, $u,v \in S$, $u \ne v$, and $|\beta| = |\delta|$.
The hint you were given to construct the grammar also tells you how to construct the automaton. The idea is to use the counter to encode the length of the prefix $\beta$ and the postfix $\delta.$ That is all. The sole addition is that you must also recognize whether $(u,v) = (a,b)$ or $(u,v) = (b,a).$
Imagine the states as two parallel segments/chains of five states each, arranged in a horizontal line if you will. In addition to these two segments there is a start state and an accepting state for a total of twelve states. The start state connects with an $\epsilon$-transition to the top segment and another $\epsilon$-transition to the bottom one. The top one corresponds to $(u,v) = (a,b)$ and the bottom one to $(u,v) = (b,a).$ The first state of each segment counts the symbols in the prefix by pushing $g$ onto the stack, then it $\epsilon$-transitions to the next state in the segment, which has a transition on $a$ to its neighbor, which loops on $a$ and $b$ without counting anything and $\epsilon$-transitions to its right neighbor, which transitions on $b$ to its neighbor, which decrements the counter by popping the symbol $g$ of the stack and transitions to the accepting state on seeing the bottom marker "#". The second (lower) segment works the same way with $a$ and $b$ reversed.
Remark. You can make do with just five total states if you allow a non-deterministic transition function which eliminates the need for the inner transitions on $\epsilon$. Count the length of the prefix in the start state, transition non-deterministically on $a$ to the upper segment, now consisting of only one state, and on $b$ to the lower segment. Loop without counting in each segment and transition on $b$ from the upper state and $a$ from the lower to a common state that decrements the counter and transitions to the accepting state on seeing the marker.
Addendum. Depending on your model you may want to transition out of the accepting state into a rejecting state on seeing extra symbols. It is possible also to merge the last states of the two chains from the first solution, since both do the same thing, i.e. reduce the counter and the pair of non-matching $(u,v)$ has already been found.