Mostrar Mensajes

Esta sección te permite ver todos los posts escritos por este usuario. Ten en cuenta que sólo puedes ver los posts escritos en zonas a las que tienes acceso en este momento.

Mensajes - nosferacento

Páginas: 1 2 3 4 [5] 6 7 8 9 10 ... 23

De todo un poco... / lenguaje con alfabeto 0,1 y número par de 0´s o exactamente dos 1´s

« en: 17 de Junio 2014, 11:06 »

PREGUNTA: Dado el alfabeto Σ = {0, 1}, el lenguaje L se define como L = {w | w contiene un número par de 0's, o exactamente dos 1 's }. Indicar qué expresión regular genera el lenguaje L:

a) (1*01*01*0*) + (0*10*10*)

b) (1*01*01*)* + (0*10*10*)

c) (10101)* + (0*10*10*)

RESPUESTA: la opción correcta es la b).

Analizamos la opción a). Nos permite generar 000 y esta cadena no contiene un número par de ceros ni exactamente dos unos, por lo que descartamos la opción a).

Analizamos la opción b). El sumando izquierdo implica que se admite la cadena vacía, que tiene cero 0´s. El número cero se considera par, por tanto se admite. El sumando izquierdo obliga a que el número de ceros sea siempre par si se escoge este sumando. El sumando derecho siempre tiene dos 1´s. Esta expresión regular genera un lenguaje como el indicado.

Analizamos la opción c). El sumando izquierdo implica que se admite la cadena vacía, que tiene cero 0´s. El número cero se considera par, por tanto se admite. En otro caso, el sumando izquierdo siempre tiene un número par de ceros. El sumando derecho es igual que el de la opción b, siempre tiene dos 1´s.

Se podría responder la b) o la c), al menos los lenguajes que generan b) y c) cumplen con los criterios del lenguaje, ahora bien, ¿representan exactamente el lenguaje o a un subconjunto del lenguaje? Para responder esto nos ponemos cadenas mínimas del lenguaje y nos preguntamos qué opción permite generarlas:

Cadena vacía: la generan la opción b) y c).

Cadena 11: la generan la opción b) y c).

Cadena 00: la genera b) pero no la genera c). Por tanto b) representa el lenguaje mientras que c) representa un subconjunto del lenguaje.

Nota: pregunta sutil, hemos de responderla analizando detenidamente las expresiones y recurriendo a cadenas de prueba.

De todo un poco... / relación entre un autómata a pila y una gramática

« en: 15 de Junio 2014, 19:54 »

PREGUNTA: Dado el lenguaje L generado por la siguiente gramática:

S -- > xSy | xSyy | z

y el siguiente autómata (Nota: Se supone que la pila se encuentra inicialmente vacía. En el diagrama de transiciones algunos arcos tienen una etiqueta en la que el segundo elemento es ε. En estos casos se considera que el autómata ejecuta esta transición teniendo en cuenta únicamente el símbolo actual de la cadena de entrada sin inspeccionar el contenido de la cima de la pila. Por tanto, en estas transiciones no se extrae ningún elemento de la pila):

¿Qué función realiza la pila del autómata en relación a las cadenas del lenguaje L?

a) Lleva la cuenta del número de x's presentes en las cadenas del lenguaje L.

b) Lleva la cuenta del número de y's presentes en las cadenas del lenguaje L.

c) Lleva la cuenta del número de z's presentes en las cadenas del lenguaje L.

d) Lleva la cuenta del número de producciones necesarias para derivar las cadenas del lenguaje L.

RESPUESTA: la opción correcta es la d).

Las cadenas del lenguaje L son

a) xzy, xxzyy, xxxzyyy, … es decir, un cierto número de x´s seguidas de una z y luego el mismo número de z´s que x´s hubieran aparecido previamente.
b) xzyy, xxzyyyy, xxxzyyyyyy … es decir, cierto número de x´s seguido de una z y a continuación el doble número de y´s que de x´s hubieran aparecido previamente.

c) z (cadena mínima admitida por la gramática)

El autómata de la figura es no determinista ya que tiene dos transiciones posibles para una misma entrada y símbolo en cima de pila.

Por la rama de q0-q1 no puede reconocer ninguna cadena de L, ya que tras recibir una x no tiene transición definida para la z, y si recibe una z no llega a aceptación.

Por la rama de q0-q2 la única cadena que puede reconocer es xzy. En este caso al leer la x pone una a en la pila y al leer la z pone otra a en la pila, dejando la pila con dos a´s. Dos a´s no son el número de x´s, de z´s ni de y´s de la cadena. Por tanto descartamos a), b) y c).

¿Cuáles son las producciones necesarias para derivar xyz?

1 S -- > xSy
2 S -- > z

Se deriva xSy y de ahí xzy.

Por tanto la pila ha contado el número de producciones necesarias y respondemos la opción d).

Esta pregunta podemos calificarla de extraña, porque atribuirle un papel a la pila del autómata cuando éste sólo puede reconocer una cadena del lenguaje es un poco… extraño.

Otra forma de razonarlo: cada x implica una producción y cada z implica también una producción. El autómata apila una a con cada x ó cada z, por tanto está contando el número de producciones.

De todo un poco... / concepto de lenguaje recursivamente enumerable y lenguaje NRE

« en: 14 de Junio 2014, 10:10 »

PREGUNTA: Indique cuál de las siguientes afirmaciones es verdadera:

a) Dado un alfabeto Σ, para cualquier lenguaje construido sobre Σ existe una máquina de Turing que lo acepta

b) Dado un alfabeto Σ, cualquier lenguaje construido sobre Σ es recursivamente enumerable

c) Dado un alfabeto Σ, existen lenguajes construidos sobre Σ que no son recursivamente enumerable s y para los cuales no se puede construir una máquina de Turing que los acepte.

RESPUESTA: la opción correcta es la c).

Las máquinas de Turing son las máquinas abstractas con mayor capacidad de reconocimiento de un lenguaje (y capacidades computacionales análogas a las de un computador) pero esto no significa que tengan capacidad para reconocer todos los lenguajes. De hecho, los lenguajes no reconocidos por máquinas de Turing se denominan lenguajes no recursivamente enumerables. La opción a) queda descartada.

De acuerdo con la explicación anterior la opción b) realmente es equivalente a la opción a) y por tanto la descartamos.

Respondemos por tanto la opción c).

De todo un poco... / autómata determinista o no determinista y bien definido o mal definido

« en: 10 de Junio 2014, 17:37 »

PREGUNTA: ¿Qué podemos afirmar del siguiente autómata?

a) Es un autómata no determinista que reconoce cadenas de x e y de tamaño mayor o igual a dos.

b) Está mal definido, ya que tiene dos estados de aceptación.

c) No tiene en cuenta la cantidad de símbolos z que se leen de la cadena de entrada.

d) Ninguna de las anteriores.

RESPUESTA: la opción correcta es la c).

¿Es un autómata determinista o no determinista? Es un autómata determinista, puesto que no hay dos transiciones definidas para un mismo carácter de entrada. Por ello descartamos la opción a).

¿Está mal definido por tener dos estados de aceptación? No tiene por qué, un autómata puede tener ninguno, uno o más de un estados de aceptación.

¿Tiene en cuenta la cantidad de símbolos z que se leen de la cadena de entrada? El autómata puede llegar a aceptación con cero, uno o más de un símbolo z en la cadena de entrada. Por tanto la respuesta a la pregunta anterior es no.

La pregunta resulta un tanto confusa porque nos podemos preguntar si el autómata acepta la cadena zx y la respuesta es no, y esto pareciera dar a entender que sí se tiene en cuenta entonces la cantidad de símbolos z´s. Pero el autómata rechaza zx no porque tenga en cuenta el número de z´s en la cadena de entrada, sino porque la cadena no está contemplada como cadena del lenguaje definido.

De todo un poco... / capacidad de un autómata para devolver un resultado ordenando

« en: 09 de Junio 2014, 12:11 »

PREGUNTA: Indicar cuál es el autómata más sencillo (con menor capacidad de reconocimiento) que funcione de la siguiente manera. Dada cualquier cadena de x e y, substituya todas las x's por z's y devuelva una cadena con todas las y's al principio y las z's a continuación

a) Un autómata finito.

b) Un autómata a pila determinista.

c) Un autómata a pila no determinista.

d) Una máquina de Turing.

RESPUESTA: la opción correcta es la d).

Dado que el autómata ha de devolver algo, necesitamos un autómata que pueda devolver un resultado. Esto tendría que hacerse a través de una pila donde quede reflejado el resultado, o a través de una cinta de una máquina de Turing. Por tanto descartamos la opción a) Un autómata finito ya que estos autómatas no pueden devolver (al menos de forma explícita) un resultado.

Pensemos en un ejemplo. Si recibimos xyxyxxxyyy el autómata primero ha de leer todos los caracteres para sustituir las x´s por z´s, en este ejemplo zyzyzzzyyy. Después tiene que devolver una cadena con todas las y´s al principio y las z´s al final, en este ejemplo yyyyyzzzzz

Un autómata a pila puede introducir en la pila una z por cada x leída y una y por cada y leída. Una vez leída la cadena un autómata a pila no puede volver atrás, aunque sí podría realizar transiciones espontáneas sin consumir caracteres (leyendo la cadena vacía y modificando la pila). Pero pudiendo explorar sólo la cima de pila, no tendríamos forma de realizar una ordenación como la requerida (donde necesitaríamos poder enviar las y´s al final de la estructura de datos, pero una pila no nos permite hacer esto). Descartamos las opciones b) y c) por tanto.

Una máquina de Turing tiene la misma capacidad de computación que un computador y puede realizar esta tarea sin problema. Respondemos por tanto la opción d).

De todo un poco... / lenguaje generado por una gramática y sus características

« en: 08 de Junio 2014, 17:20 »

PREGUNTA: Sea L el lenguaje generado por la siguiente gramática:

S -- > xxSyy | xy

Indicar cuál de las siguientes afirmaciones es verdadera:

a) L está formado por cualquier cadena que tenga el mismo número de x's que de y's.

b) L está formado por cualquier cadena que tenga el mismo número de x's que de y's, y que además tenga un número par de símbolos.

c) L está formado por cualquier cadena que tenga el mismo número par de x's y de y's.

d) Ninguna de las anteriores afirmaciones es verdadera.

RESPUESTA: la opción correcta es la d).

La opción a) es falsa puesto que la gramática impone que las x´s han de venir antes que las y´s, por tanto cualquier cadena con el mismo número de x´s que de y´s no será válida. Por ejemplo yyxx no es válida.

La opción b) es falsa por el mismo motivo.

La opción c) es falsa por el mismo motivo, además el número de x´s o de y´s puede no ser par (aunque la cadena en su conjunto sí tenga un número de símbolos par.

Respondemos por tanto la opción d).

De todo un poco... / cómo saber si un lenguaje es regular o no lo es

« en: 05 de Junio 2014, 10:41 »

PREGUNTA: Indicar cuál de los siguientes lenguajes NO es regular:

a) L = {w ∈ {a, b}* | abab es subcadena de w}

b) L = {w ∈ {a, b}* | w ∉ {aⁿbⁿ} : n > 0}

c) El lenguaje consistente en las cadenas de caracteres tales que dos a's están separadas por 4i símbolos para algún entero i >= 0

RESPUESTA: la opción correcta es la b).

Recordar que lenguaje no regular es el que:

a) No cumple el lema de bombeo para lenguajes regulares
b) No puede ser representado con un autómata finito
c) Necesita una pila o cinta para “recordar”

El lenguaje de la opción a) podemos expresarlo como (a+b)*abab(a+b)* y resulta un lenguaje regular, o al menos lo parece.

El lenguaje de la opción b) requiere contar el número de a´s y comprobar que no es igual al número de b´s. Necesitamos la capacidad de contar, y no podemos basarnos en un número finito de posibilidades porque el número de a´s y b´s es ilimitado. Por tanto no se puede representar con un autómata finito y no es un lenguaje regular.

El lenguaje de la opción c) podría representarse con un autómata que admite cualquier carácter en su estado inicial q0, y cuando recibe una a se mueve a un estado q1, un carácter distinto de a lleva a q2, otro carácter distinto de a mueve a q3 y con el siguiente carácter distinto de a mueve a q4. Para salir de q4 si el carácter recibido es distinto de a se vuelve a q0, y en caso de ser a se vuelve a q1

Serían estados de aceptación q0 (ya que se admite i=0)

No serían estados de aceptación q1, q2, q3, q4

Si es representable con un autómata finito el lenguaje es regular. La definición de este lenguaje no es del todo clara, pero parece que se adaptaría a la definición de lenguaje regular.

Respondemos por tanto la opción b).

C, C++, C#, Java, Visual Basic, HTML, PHP, CSS, Javascript, Ajax, Joomla, MySql y más / Re:preguntas examen programación orientada a objetos Ingeniería Informática UNED

« en: 03 de Junio 2014, 18:54 »

Gracias a tí, como ya he comentado estos comentarios son de agradecer... Trato de ir ampliando y mejorando el material de esta y otras asignaturas, pero requiere su esfuerzo. Suerte a todos los que han hecho o van a hacer próximamente exámenes...

De todo un poco... / propiedades de los lenguajes libres de contexto estrella de Kleene

« en: 01 de Junio 2014, 21:40 »

PREGUNTA: La estrella de Kleene o clausura de un lenguaje independiente de contexto, ¿es siempre un lenguaje independiente de contexto?

a) Sí, siempre

b) No, nunca

c) Depende de los casos

RESPUESTA: la opción correcta es la a).

Para responder a esta pregunta tenemos que recordar lo siguiente. Los lenguajes independientes del contexto (LIC) son cerrados para la unión, concatenación, clausura o estrella de Kleene, clausura positiva (+), homomorfismo y reflexión. Es decir, la unión de dos LIC da por resultado un LIC, la concatenación de dos LIC da como resultado un LIC, la estrella de Kleene aplicada a un LIC da como resultado un LIC, etc.

Diferencia entre las propiedades de los LIC y de los lenguajes regulares: la intersección de dos lenguajes regulares es regular, pero la de dos LIC no tiene por qué ser un LIC.

Además el complementario de una expresión regular es regular, pero el complementario de un LIC no tiene por qué ser un LIC.

De todo un poco... / etiquetas requeridas para que un autómata acepte expresión regular

« en: 31 de Mayo 2014, 12:59 »

PREGUNTA: Dada la siguiente expresión regular: (((a + b) c* (a + b)) + (( ac + ab) *))* y el siguiente autómata finito:

Indicar qué valores deben tener Etiqueta-1 y Etiqueta-2 para que el autómata acepte el mismo lenguaje que la expresión regular:

a) Etiqueta-1=a, b Etiqueta-2=a

b) Etiqueta-1=c Etiqueta-2=a

c) Etiqueta-1=a Etiqueta-2=a, b

d) Ninguna de las anteriores combinaciones es válida

RESPUESTA: la opción correcta es la c), aunque ver comentarios.

Nos dice que el autómata debe aceptar el mismo lenguaje, pero esto no deja claro si debe ser exactamente el mismo lenguaje, o podría reconocer un lenguaje más amplio que englobe el lenguaje de la expresión regular. Si se considerara oportuno, se podría incluir un comentario en el examen para indicar qué interpretación hemos hecho.

Nos fijamos primero en si la expresión regular admite ε, ya que el autómata admite ε por ser el estado inicial un estado de aceptación. Dado que el conjunto de la expresión regular está afectada por un asterisco de Kleene, efectivamente admite ε.

La expresión regular y el autómata no son fáciles de analizar con un simple vistazo, requiere un tiempo y posiblemente se pueda hacer de distintas maneras.

( ac + ab) * está contenido en la rama de abajo del autómata.

((a + b) c* (a + b)) está contenido en la rama de arriba del autómata.

Para ligar la rama de arriba con la de abajo necesitamos que etiqueta-1 sea a ya que la rama de abajo sólo admite comienzos por la letra a, mientras que para ligar la de abajo con la de arriba necesitamos que etiqueta-2 sea a,b ya que la rama de arriba admite inicios tanto con a como con b.

Otra forma de razonarlo: plantear cadenas que admite la expresión regular y ver qué valores de etiquetas se requerirían en el autómata:

La ER admite acccaac: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 en principio nos da igual.

La ER admite acccaab: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 en principio nos da igual.

La ER admite abacccb: no intervienen las etiquetas

La ER admite acbac: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 en principio nos da igual.

La ER admite acbacbb: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 ha de ser Etiqueta-2=b.

Vemos que la Etiqueta-1 ha de ser a. La Etiqueta-2 tendría que ser b. Respondemos entonces la opción c). Esta pregunta tiene su complejidad, no permite de forma clara tener seguridad de que la conclusión a la que llegamos sea con certeza la correcta.

De todo un poco... / lenguaje generado por una gramática con paréntesis y circularidad

« en: 29 de Mayo 2014, 09:16 »

PREGUNTA: Considere la gramática de símbolos terminales {(, ), ; , 1,2, 3}, símbolos no terminales {S, A, E} y producciones:

S --> (A)
A --> A;E | E
E --> 1 | 2 | 3 | S

La gramática genera listas de elementos que son números o a su vez listas separadas por el símbolo ";". Indicar cuál de las siguientes afirmaciones es verdadera:

a) El lenguaje es regular

b) El lenguaje es independiente del contexto no regular

c) No existe una gramática equivalente en Forma Normal de Chomsky

RESPUESTA: la opción correcta es la b)

Estudiamos la gramática propuesta y tratamos de ver qué cadenas genera:
Si en S --> (A) sustituimos A podemos tener:
(A;E) y a su vez ((A);E) y a su vez (((A));E) … que nos lleva a una salida de tipo (((1));2)

Por tanto podemos generar (numero;numero), ((numero);numero), (((numero));numero) … etc.

Tenemos que fijarnos en una cosa: los paréntesis están balanceados, es decir, por cada paréntesis de apertura tiene que haber un paréntesis de cierre.

Podemos intentar describir una expresión regular, pero nos vamos a encontrar con que no nos es posible hacer que los paréntesis se balanceen. Por ejemplo (usamos corchetes para indicar agrupación y diferenciarlo del carácter paréntesis):

[(numero;numero)] | [ ( [(numero)]+;numero) ]

Nos llevaría a cadenas como ((3)(1);2) donde se generan paréntesis balanceados pero insertando siempre un número con paréntesis detrás de otro.

Para balancear paréntesis como hace la gramática necesitamos contar, y la máquina más básica con capacidad para contar es un autómata a pila, ya que los autómatas finitos (lenguajes regulares) no tienen capacidad para contar. Por tanto la opción a) es falsa, no es un lenguaje regular.

Con un autómata a pila podemos generar este lenguaje, por tanto es un lenguaje independiente del contexto no regular. Provisionalmente vamos a responder la b), pero antes examinemos la opción c).

Si el lenguaje contiene la cadena vacía ε no existirá gramática equivalente en forma normal de Chomsky (FNC) sino una gramática en forma normal de Chomsky que genera L – { ε }, por tanto una cuestión a estudiar es si la gramática contiene la cadena vacía. Ya a primera vista podemos responder que no, la gramática no contiene la cadena vacía ya que la derivación inicial de S nos obliga a que la cadena más corta lleve como mínimo los paréntesis de apertura y cierre. Por tanto sí existe una gramática en FNC y podemos decir que la opción c) es falsa.

Respondemos por tanto la opción b)

De todo un poco... / examen resuelto autómatas, gramáticas y lenguajes

« en: 28 de Mayo 2014, 08:34 »

Con las últimas diez preguntas hemos completado un examen, que normalmente consta de diez preguntas tipo test. Es conveniente que se trate de resolver el examen haciendo una simulación de examen real, controlando el tiempo empleado y respondiendo todas las preguntas a la vez sin consultar ningún tipo de documentación, y luego comprobar cómo nos hubiera ido en ese caso supuesto "real" y qué nota habríamos sacado. Para quien quiera intentarlo, dejo el examen con enunciados completos en el archivo adjunto a este post (archivo jun11_1a_sem_A.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...

De todo un poco... / propiedades de los lenguajes independientes del contexto

« en: 27 de Mayo 2014, 09:30 »

PREGUNTA: El resultado de concatenar dos lenguajes independientes de contexto, ¿es siempre un lenguaje independiente de contexto?

a) Sí, siempre

b) No, nunca

c) Depende de los lenguajes que se consideren

RESPUESTA: la opción correcta es la a).

Para responder a esta pregunta tenemos que recordar lo siguiente. Los lenguajes independientes del contexto (LIC) son cerrados para la unión, concatenación, clausura o estrella de Kleene, clausura positiva (+), homomorfismo o reflexión. Es decir, la unión de dos LIC da por resultado un LIC, la concatenación de dos LIC da como resultado un LIC, etc.

Diferencia entre las propiedades de los LIC y de los lenguajes regulares: la intersección de dos lenguajes regulares es regular, pero la de dos LIC no tiene por qué ser un LIC.

Además el complementario de una expresión regular es regular, pero el complementario de un LIC no tiene por qué ser un LIC.

De todo un poco... / lenguaje generado por una gramática con ceros y unos

« en: 26 de Mayo 2014, 17:17 »

PREGUNTA: Dada la siguiente gramática G:

S -- > A1B
A -- > 0A | ε
B -- > 0B | 1B | ε

y la expresión regular E = 0*1 (0 + 1) * . Indicar cuál de las siguientes afirmaciones es verdadera:

a) G y E no pueden generar el mismo lenguaje porque la gramática es independiente del contexto (y por tanto, generará un lenguaje independiente del contexto) y la expresión regular generará un lenguaje regular

b) Ambos reconocen el mismo lenguaje

c) Ninguna de las anteriores afirmaciones es verdadera

RESPUESTA: la opción correcta es la b).

Si analizamos el lenguaje generado por la gramática tenemos que la palabra más corta aceptada es 1, y que se pueden generar cadenas con tantos ceros iniciales como se desee y con tantos ceros o unos finales intercalados como se desee. Esto lo podemos representar con una expresión regular: 0* 1 (0+1)*, por tanto la gramática y la expresión regular generan el mismo lenguaje y la opción cierta es la b).

Nota: si nos preguntara ¿es esta gramática regular? La respuesta sería no, porque para una gramática ser regular debe cumplir:

- En el lado izquierdo de las reglas solo puede haber un único símbolo no terminal
- En el lado derecho puede aparecer: un símbolo terminal, un símbolo terminal seguido de un no terminal ó el símbolo de cadena vacía. La producción S - > A1B no cumple con estas normas, por tanto la gramática no es regular.

Sin embargo, el hecho de que una gramática no sea regular no obligatoriamente implica que no genere un lenguaje regular, de hecho en este caso la gramática no es regular y sin embargo genera un lenguaje regular.

Recordar que todos los lenguajes regulares son a su vez lenguajes independientes del contexto.

De todo un poco... / lenguaje de máquinas de turing de varias cintas o no deterministas

« en: 25 de Mayo 2014, 22:10 »

PREGUNTA: Dado un alfabeto Σ, llamamos L1 al conjunto de lenguajes de Σ aceptados por máquinas de Turing deterministas de una sola cinta, L2 al conjunto de lenguajes de Σ aceptados por máquinas de Turing deterministas con varias cintas y L3 al conjunto de lenguajes de Σ aceptados por máquinas de Turing no deterministas y con varias cintas

¿Cuál de las siguientes afirmaciones es verdadera?

a) L1 = L2 ⊂ L3

b) L1 ⊂ L2 = L3

c) Ninguna de las afirmaciones anteriores es cierta

RESPUESTA: la opción correcta es la c).

Todas las máquinas de Turing, independientemente del número de cintas de que consten o de que sean deterministas o no, tienen la misma capacidad de reconocimiento de lenguajes y los lenguajes que reconocen se denominan Lenguajes Recursivamente Enumerables (LRE). El número de cintas puede variar la eficiencia u orden de complejidad con que una máquina te Turing resuelve un cómputo, pero no modifica los lenguajes reconocibles. Por tanto L1 = L2 = L3

Y ninguna de las afirmaciones anteriores es cierta. La opción correcta es la c).

De todo un poco... / lenguaje formado por número par de x´s seguido por mismo número de y´s

« en: 24 de Mayo 2014, 19:29 »

PREGUNTA: Dado el lenguaje L generado por la siguiente gramática:

S -- > xxSyy | xxyy

y el siguiente autómata (Nota: Se supone que la pila se encuentra inicialmente vacía):

Indicar cuál de las siguientes afirmaciones es verdadera:

a) El autómata no comprueba que haya un número par de y's en las cadenas del lenguaje L.

b) El autómata no reconoce todas las cadenas contenidas en el lenguaje L.

c) El autómata reconoce todas las cadenas contenidas en el lenguaje L.

d) El autómata no está correctamente definido.

RESPUESTA: la opción correcta es la c).

Las cadenas del lenguaje L son cadenas con un número de caracteres par y formadas por el mismo número de x´s que de y´s. El lenguaje no admite la cadena vacía, siendo la cadena más corta admitida xxyy.

El autómata desde S pone z en cima de pila y pasa al estado X, donde permite leer un número par de x´s poniendo una a en cima de pila por cada x leída. Cuando se lee una y se desapila una a y se pasa al estado Y. Ahí se elimina una a de la pila por cada carácter y recibido. Si la pila está vacía se pasa al estado de aceptación F.

Opción a): es falsa. Si el autómata no verifica que hay un número par de y´s, además siendo el número de x´s igual al de y´s, entonces no pasa a aceptación.

Opción b): es falsa. El autómata sí reconoce todas las cadenas del lenguaje.

Opción c) es verdadera.

Opción d) es falsa.

De todo un poco... / valor que deben tomar etiquetas en un autómata

« en: 23 de Mayo 2014, 09:04 »

PREGUNTA: Indicar para qué valores de las etiquetas Etiqueta-1 y Etiqueta-2, el autómata de la figura representa el lenguaje {xⁿ⁺¹ yⁿ : n >=0}. Se supone que inicialmente la pila se encuentra vacía y que el símbolo inicial de la pila es Zo.

a) Etiqueta-1= x, ε; z Etiqueta-2= ε, z; ε

b) Etiqueta-1 = x, ε; y Etiqueta-2 = ε, ε; ε

c) No existen valores de Etiqueta-1 y Etiqueta-2 que hagan correcta la solución

RESPUESTA:

Si nos fijamos en q2, por cada y leída se quita una z de la pila. Si necesitamos que el número de x´s sea uno más que el de y´s, nos interesa un autómata no determinista que consuma x´s en q1 añadiendo z´s a la pila, pero que lea una x sin añadir z a la pila para hacer la transición a q2. De esta manera, en la pila nos quedan un número de z´s que es igual al de x menos una. En q2 se desapila una z con cada carácter y leído y al vaciar la pila se pasa a aceptación en q3. Por tanto Etiqueta-1 debe añadir z´s a la pila, y debería ser x, ε; z para reconocer la primera x, junto a x, z; zz para reconocer las x´s adicionales.

Etiqueta 2 debería ser x, z; z para reconocer la última x.

Con la opción a) etiqueta 1 consume x´s dejando una z en la cima de pila y etiqueta 2 lleva a q2 de forma espontánea eliminando la z en la cima de pila, pero esto no asegura que el número de x´s leído sea uno más que el número de y´s.

Con la opción b) se consumen x´s dejando una y en cima de pila y se pasa a q2 donde no habría transición posible al no existir una z en cima de pila.

Por tanto respondemos la opción c), ninguna de las alternativas planteada es válida.

De todo un poco... / lenguaje de cadenas con numero par de x´s e y´s y autómata a pila

« en: 22 de Mayo 2014, 12:01 »

PREGUNTA: Considere el lenguaje L generado por la siguiente gramática:

S -- > xxSyy | ε

y el siguiente autómata (Nota: Se supone que la pila se encuentra inicialmente vacía):

¿Qué significado se le puede atribuir al estado par cuando el autómata lee cadenas del lenguaje L?

a) Se llega al estado par cuando se ha leído un número par de x's en las cadenas del lenguaje L.

b) Se llega al estado par cuando se ha leído un número par de símbolos en las cadenas del lenguaje L.

c) Se llega al estado par cuando se ha leído un número par de y's en las cadenas del lenguaje L.

d) Se llega al estado par cuando se ha leído un número impar de x's en las cadenas del lenguaje L.

RESPUESTA:

Las cadenas del lenguaje L son cadenas con un número de caracteres par y formadas por el mismo número de x´s que de y´s.

Si analizamos lo que hace el autómata a pila, cuando lee una x pasa al estado par y escribe una a como cima de pila. Con la siguiente x vuelve al estado S, con la siguiente x vuelve al estado par… y así sucesivamente hasta que empiece a leer las y´s. Por tanto se llega al estado par cuando se ha leído un número impar de x's en las cadenas del lenguaje L. Es decir, la opción correcta es la d).

La pregunta es sencilla siempre que no nos liemos con el nombre del estado. Que el estado se llame par no tiene necesariamente que tener un significado, también se podría haber llamado “manzana”.

De todo un poco... / lenguaje expansión decimal del número pi frente a otros

« en: 16 de Mayo 2014, 12:41 »

PREGUNTA: Indicar cuál de los siguientes lenguajes NO es regular:

a) L = {w ∈ {a, b}* | ab y ba son subcadenas de w}

b) L = {w ∈ {a, b}* | bbb no es subcadena de w}

c) El lenguaje de cadenas que son prefijos (finitos) de la expansión decimal del número pi (π), es decir, L = {3.1 ,3.14, 3.141 ,3.1415, ... }

RESPUESTA: la opción correcta es la c).

La definición de los lenguajes es un poco “extraña” y se puede interpretar así. Para la opción a, se trata del lenguaje (ab)* con la condición de que ab y ba estén presentes dentro de las cadenas del lenguaje (sin importarnos en qué posición).

Opción a): Esto se puede expresar como expresión regular tipo ya que el número de posiciones posibles de ab y ba es un número finito. Podemos tener ab – otro – ba, ab – ba – otro, ba – otro – ab, ba – ab – otro, otro – ab – ba, otro – ba – ab … y estas combinaciones se pueden expresar como (ab (ab)* ba | abba (ab)* | ba (ab)* ab | … etc.

Otra forma de razonarlo: ¿podemos dibujar un autómata finito que reconozca el lenguaje? Sí, basta un autómata que tenga dos ramas: una de ellas que contemple la posibilidad de recibir ab primero y ba después, y la otra que contemple la posibilidad de recibir ba primero y ab después.

Opción b: lo podemos representar con un autómata finito cuyo lenguaje es a, b y cuyo estado inicial es aceptación, con toda a vuelve al estado inicial, mientras que con tres b´s va a un estado muerto (del que no puede salir).

Opción c: la expansión decimal de pi genera infinitos prefijos finitos, y esto no lo podemos representar con un autómata finito. Por tanto, respondemos la opción c).

Otra forma de razonarlo es que un lenguaje infinito para ser regular ha de cumplir el lema de bombeo. En este caso no lo cumple: no podemos subdividir y bombear parte de la cadena y seguir perteneciendo la cadena al lenguaje, luego no es regular

100

De todo un poco... / diferencias entre máquinas de Turing, autómatas finitos y autómatas a pila

« en: 10 de Mayo 2014, 13:41 »

PREGUNTA: Las máquinas de Turing se diferencian de los autómatas finitos y de los autómatas a pila en que:

a) En las máquinas de Turing la cabeza lectora puede retroceder

b) Las máquinas de Turing pueden escribir sobre su cinta

c) Las dos afirmaciones anteriores son ciertas

RESPUESTA: la opción correcta es la c). Los autómatas a pila y los autómatas finitos no tienen cabeza lectora que pueda retroceder ni tienen cinta.

La opción a es cierta y la opción b es cierta, por tanto respondemos la opción c).

Páginas: 1 2 3 4 [5] 6 7 8 9 10 ... 23

Foros aprenderaprogramar.com
Didáctica y divulgación de la programación

Noticias: