Stack automata with nonequality

Question

I encontered the following problem that I'm unable to solve. The goal is to construct a stack automata, that accepts language $$ L = \left\{u\mathrm{\underline{c}}v \mid u,v \in \{\mathrm{\underline{a}},\mathrm{\underline{b}}\}^* \text{ and } u \neq v \right\} \subset \{\mathrm{\underline{a}},\mathrm{\underline{b}},\mathrm{\underline{c}}\}^* $$ I tried everything, but nothing works. I hit the problem of having just a stack, not a queue...

Answer 1

A word is in the language, if it satisfies

• It contains more than one or no $c$,
• $|u|\neq |v|$, or
• the $k$-th character of $u$ and $v$ are different for some $k$.

This leads to the following automaton:

1. Read $a$'s and $b$'s, counting them on the stack. (If a $c$ appears in this phase, go to 2.)
2. At some point (determined nondeterministically), stop counting and remember the last symbol counted.

3. After encountering the first $c$, start to count down the stack.

   3.1. If the word ends before the first $c$, discard.

   3.2. If a second $c$ is encountered, discard.

   3.3. If the word ends, before the stack is empty, accept.

4. When the stack is empty, compare the last character read to the one remembered. If they agree, discard.
5. If the remaining word does not contain another $c$, accept.

(Note that discarding for a nondeterministic automaton only means that the specific computation failed. It does not imply that the word is not in the language.)