palindromes. Based on $ {\mathtt{PAL}}$, the following promise problem is defined: $ {\mathtt{PAL \mbox{-} NPAL}}$ composed of

-   $ {\mathtt{PAL \mbox{-} NPAL_{yes}}}= \{ x 0 y \mid x \in {\mathtt{PAL}}, y \not\in {\mathtt{PAL}}\} $ and

-   $ {\mathtt{PAL \mbox{-} NPAL_{no}}}\mspace{7.1mu} = \{ x 0 y \mid x \not\in {\mathtt{PAL}}, y \in {\mathtt{PAL}}\} $.

It was shown that $ {\mathtt{PAL \mbox{-} NPAL}}$ can be recognized by 2QCFAs exactly but in exponential time and bounded-error 2PFAs can recognize $ {\mathtt{PAL \mbox{-} NPAL}}$ only if they are allowed to use a logarithmic amount of memory. Now we show that $ {\mathtt{PAL \mbox{-} NPAL}}$ can be recognized by realtime Las Vegas AfAs and so also by AfAs with restart in linear expected time.

The promise problem $ {\mathtt{PAL \mbox{-} NPAL}}$ can be solved by Las Vegas AfA $ A $ with any success probability $ p < 1 $.

It is known that AfAs can recognize $ {\mathtt{PAL}}$ with one-sided bounded-error [@VilY16A; @YS10B] and so we can design a Las Vegas automaton for $ {\mathtt{PAL \mbox{-} NPAL}}$ by using similar ideas given in [@RasY14A; @GefY15A].

The automaton $ A $ has 5 states $ S = \{ s_1,\ldots,s_5 \} $ where $ s_1 $ 