Dibujo de una PDA para un idioma

Question

Estoy iniciando a mí mismo en el TOC y el uso de una especie de azar de los recursos de la web. Estaba buscando en este problema de una Berkeley conjunto de problemas: Construir una PDA para aceptar $$ L = {a^ib^j|i \neq j , 2i \neq j} $$ Y no entiendo la solución dada aquí.(Problema 4) http://www.cs.berkeley.edu/~isabelle/cs302/ps3-soluciones.pdf

Cuando podemos decir de esta máquina acepta una cadena de caracteres? Desde mi entender, parece aceptar ab aabb,aaabbb etc así cuando no debe.

Answer 1

Hay varias definiciones diferentes de empuje hacia abajo autómatas que difieren en los detalles de la aceptación de la condición. Una condición común que (presumiblemente) en uso aquí es que una palabra es aceptada si:

1. El empuje hacia abajo de los autómatas, llega en un estado aceptante,
2. La pila está vacía.

Si usted sigue el comportamiento del autómata en la respuesta, usted encontrará que las palabras $a^ib^i$ o $a^ib^{2i}$, si se llega a un estado final, la pila no esté vacía, así que la palabra no es aceptada.