181
De todo un poco... / autómatas a pila deterministas y no deterministas
« en: 29 de Noviembre 2013, 09:42 »
PREGUNTA: Dado el alfabeto Σ = {0, 1}, sea el lenguaje L = {0n1m : n <= m}. Indicar cuál de las siguientes afirmaciones es VERDADERA:
a) Es posible construir un autómata a pila determinista que reconoce L
b) L es un lenguaje regular
c) Cualquier autómata a pila que reconozca L debe ser no determinista
RESPUESTA: la opción correcta es la a).
Analizamos el lenguaje. El lenguaje comprende todas las cadenas con igual o menor número de ceros que de unos. No nos dice nada sobre cuál es el valor mínimo para n y m, por lo que supondremos que el valor mínimo es cero (no tendría sentido admitir números negativos). Con este supuesto, las cadenas admitidas comprenden: ε, 01, 0011, 000111 , 000…111… balanceados, así como 1, 11, 111, 1111, 11111… y también 011, 0111, 01111… etc.
El balanceado es posible pero no obligatorio. Vamos a tratar de expresarlo como lenguaje regular. 0*1* no garantiza que haya menor o igual número de ceros que de unos. Para garantizar esto necesitamos contar, y esto no lo pueden hacer los autómatas finitos, por lo tanto desechamos que sea un lenguaje regular.
Ahora consideremos la posibilidad de representar el lenguaje con un autómata a pila determinista. Empezaríamos en un estado q0 con una transición ε poniendo el símbolo de fin de pila Z en la pila. En un estado q1 leeríamos cualquier símbolo 0 y lo añadiríamos a la pila. Al leer un símbolo 1, pasaríamos a un estado q2 y desapilamos un cero. Por cada 1 leído en q2 desapilamos un cero. Si llega un momento en que la pila queda vacía (aparece Z) significa que al menos había tantos unos como ceros y con 1, Z; Z pasaríamos a un estado q3 donde consumimos todos los unos que puedan venir adicionalmente con transiciones 1, Z; Z. Cuando se terminen de consumir los unos una transición ε, Z; Z nos llevaría a q4 (aceptación). Este autómata es determinista (no tiene dos transiciones posibles para una entrada y símbolo de pila).
Su representación sería esta:
![](http://i.imgur.com/XAhbeLJ.png)
Por tanto:
La opción a) es verdadera.
La opción b) es falsa.
La opción c) es falsa. Quizás se pueda representar con un no determinista, pero no es cierto que cualquier autómata a pila deba ser no determinista para reconocer el lenguaje.
a) Es posible construir un autómata a pila determinista que reconoce L
b) L es un lenguaje regular
c) Cualquier autómata a pila que reconozca L debe ser no determinista
RESPUESTA: la opción correcta es la a).
Analizamos el lenguaje. El lenguaje comprende todas las cadenas con igual o menor número de ceros que de unos. No nos dice nada sobre cuál es el valor mínimo para n y m, por lo que supondremos que el valor mínimo es cero (no tendría sentido admitir números negativos). Con este supuesto, las cadenas admitidas comprenden: ε, 01, 0011, 000111 , 000…111… balanceados, así como 1, 11, 111, 1111, 11111… y también 011, 0111, 01111… etc.
El balanceado es posible pero no obligatorio. Vamos a tratar de expresarlo como lenguaje regular. 0*1* no garantiza que haya menor o igual número de ceros que de unos. Para garantizar esto necesitamos contar, y esto no lo pueden hacer los autómatas finitos, por lo tanto desechamos que sea un lenguaje regular.
Ahora consideremos la posibilidad de representar el lenguaje con un autómata a pila determinista. Empezaríamos en un estado q0 con una transición ε poniendo el símbolo de fin de pila Z en la pila. En un estado q1 leeríamos cualquier símbolo 0 y lo añadiríamos a la pila. Al leer un símbolo 1, pasaríamos a un estado q2 y desapilamos un cero. Por cada 1 leído en q2 desapilamos un cero. Si llega un momento en que la pila queda vacía (aparece Z) significa que al menos había tantos unos como ceros y con 1, Z; Z pasaríamos a un estado q3 donde consumimos todos los unos que puedan venir adicionalmente con transiciones 1, Z; Z. Cuando se terminen de consumir los unos una transición ε, Z; Z nos llevaría a q4 (aceptación). Este autómata es determinista (no tiene dos transiciones posibles para una entrada y símbolo de pila).
Su representación sería esta:
![](http://i.imgur.com/XAhbeLJ.png)
Por tanto:
La opción a) es verdadera.
La opción b) es falsa.
La opción c) es falsa. Quizás se pueda representar con un no determinista, pero no es cierto que cualquier autómata a pila deba ser no determinista para reconocer el lenguaje.