2

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...

fgp
  • 21,050
Martin Zikmund
  • 175
  • Whats is "c" supposes to be? A single character $\underline{c}$ perhaps? Or an arbitrary string from ${a,b}^*$? – fgp May 12 '14 at 11:22
  • Sorry for not specifying, we are operating on alphabet X={a,b,c} – Martin Zikmund May 12 '14 at 11:37
  • While this question is considered on-topic here, it is marginal, and you might have a better chance on [cs.se]. This is a variant of {u v | u ≠ v} and the middle $c$ makes a big difference since the proposed technique for the language without $c$ avoids determining the position of the middle. (Or would you allow an automaton with multiple stacks? In that case there's a simple 2-stack construction.) – Gilles 'SO- stop being evil' May 12 '14 at 12:24
  • @Gilles The $c$ is not required to be in the exact middle. That makes this problem easier than the one you linked. – FrankW May 12 '14 at 12:52
  • @FrankW Oh! Right. So a similar technique does work. Hmmm. Or does it? – Gilles 'SO- stop being evil' May 12 '14 at 12:54

1 Answers1

2

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.)

FrankW
  • 136