Costruzione di un bancone automatico per il complemento dei palindromi

Question

Come dovrei costruire un automobile da 1 banco non deterministico per la lingua $ l $ che è il complemento dei palindromi $ overline {l} = {ww^{rev} } $ su un simbolo 2 alfabet $ Sigma = {0,1 } $?

La definizione che sto usando per 1-NCA è composta da:

• $ S $, il set di stati,
• $ Sigma $, l'alfabeto ($ sigma = {0,1 } $ nel nostro caso),
• $ s_ {0} in s $, lo stato iniziale,
• $ F sottoseteq s tempi
• $ Delta: s tims { text {zero}, text {non zero} } tempe a destrorrow s tempe {-1,0,1 } $, la funzione di transizione.

Dato una parola $ w = x_1x_2 ldots x_ny_1y_2 ldots y_n $, so che se $ x_i $ non è uguale a $ y_ {n-i+1} $, il requisito di Palindrome non riesce. Ho la sensazione che il bancone abbia qualcosa a che fare con quella distanza tra quelle lettere, ma formalizzando questo è ciò a cui sono bloccato.

Poiché un 1-NCA è la stessa cosa di un NPDA (automobile pushdown non deterministico) con un solo simbolo nell'alfabeto dello stack, accetterei risposte usando anche tali PDA. Ciò è soprattutto perché trovo pochissimi testi che discutono di banconi.