Cómo construir un pushdown autómatas para L= { w ∈ {a, b}* | w no es igual a xx^R para algún x ∈ {a, b}* }
0
Estoy asumiendo que usted desea un no-determinista empuje hacia abajo autómata. Yo no creo que esto es posible con el determinismo de la PDA.
Esto suena como una tarea problema, así que sólo voy a dar un esquema general:
Básicamente, supongo que en el centro de la cadena. Usted inserción de elementos en la pila, hasta que en algún momento supongo que ha llegado el centro de la cuerda. Usted, a continuación, empezar a comparar su entrada a los elementos que usted está estallar fuera de la pila. Usted no si no coinciden. De tener éxito si se llega al final de la entrada exactamente como la pila está vacía.