Construction d'un comptoir automate pour le complément des palindromes

Question

Comment pourrais-je construire un automate à 1 contre déterministe pour la langue $ l $ qui est le complément du palindromes $ overline {l} = {ww ^ {Rev} } $ sur un alphabet symbole à 2 $ sigma = {0,1 } $?

La définition que j'utilise pour 1-NCAS consiste à:

• $ S $, l'ensemble des États,
• $ Sigma $, l'alphabet ($ sigma = {0,1 } $ dans notre cas),
• $ s_ {0} dans s $, l'état initial,
• $ F subseteq s time { text {zero}, text {nonzero} } $, l'ensemble d'acceptation des états, et
• $ delta: S Times { text {zero}, text {nonzero} } Times a rightarrow S Times {- 1,0,1 } $, la fonction de transition.

Étant donné un mot $ w = x_1x_2 ldots x_ny_1y_2 ldots y_n $, je sais que si $ x_i $ n'est pas égal à $ y_ {n-i + 1} $, l'exigence de palindrome échoue. J'ai le sentiment que le comptoir a quelque chose à voir avec cette distance entre ces lettres mais formaliser c'est ce que je suis coincé.

Étant donné qu'un 1-NCA est la même chose qu'un NPDA (Automaton Pushdown non déterministe) avec un seul symbole dans l'alphabet de pile, j'accepterais également des réponses en utilisant de tels PDA. C'est d'autant plus que je trouve très peu de textes discutant de Counter Automates.