Buen día Nicolás,
demás que te haya quedado claro. Normalmente la intuición es:
"Si estoy en el estado q, tengo a Z en el top del stack y el siguiente símbolo a leer es a: ¿cuántas opciones de transición tengo?".
Si la respuesta a esa pregunta es, para alguna combinación (estado,tope,entrada), "más de una opción", entonces el APD es no determinista.
Por ejemplo, fijate que en este APD (incompleto, está claro), el no-determinismo se manifiesta dos veces.
Estando en q3, teniendo a X en el tope del stack y "a" como símbolo a leer, tengo dos opciones:
- Me muevo a q4 y dejo el stack intacto
- Me muevo a q5 y dejo el stack intacto
Por otra parte, en q4, sucede que teniendo a X en el tope del stack y "b" como próximo símbolo a leer, tengo dos opciones:
- Leo la b de la entrada, me quedo en q4 y hago POP del stack
- No consumo la b de la entrada, me muevo a q6 y dejo el stack intacto.
Para cerrar, algo que comentábamos el otro día en la clase de consulta era que hay que tener cuidado con las transiciones épsilon pues por si mismas, solas, no implican no-determinismo, como sí era el caso en los Autómatas Finitos. Por ejemplo:
Entre q2 y q3 hay una transición épsilon, pero eso no implica no-determinismo: siempre tengo un único camino posible, ya sea consumiendo entrada o no.
Cualquier consulta, a las órdenes.
Saludos,
Santi
Saludos,
Santi