[2015] [Segundo Parcial] [Ejercicio 3] [Parte b]

[2015] [Segundo Parcial] [Ejercicio 3] [Parte b]

de Fernando Andres Tomeo Lussich -
Número de respuestas: 6

https://www.fing.edu.uy/inco/cursos/teoleng/parciales/SolParcial2-2015.pdf

En la solucion propuesta, se hace reconocimiento de la tira por estado final, me gustaria saber si quisiera hacerlo por stack vacio bastaria con eliminar el estado q7 y agregar al estado q6 las transicion (epsilon, X, epsilon) y (epsilon, z0, epsilon)


En respuesta a Fernando Andres Tomeo Lussich

Re: [Segundo parcial 2015] - Ejercicio 3, parte b.

de Leonardo Richero -

Si haces eso, con la transición (epsilon, z0, epsilon) de q6 a q6, estarías aceptando p=m.

La transición de q6 a q7 (epsilon, X, X) de la solución publicada esta garantizando p>m.

Si dejas q7 como estado no final y le agregas algunas transiciones seguramente consigas un APD por stack vacío que reconozca el lenguaje.

En respuesta a Leonardo Richero

Re: [Segundo parcial 2015] - Ejercicio 3, parte b.

de Fernando Andres Tomeo Lussich -

Buenas, haciendo el ejercicio y viendo la solucion propuesta, me parece que reconoce la tira 01011 la cual no pertenece al lenguaje Lb ya que p < m, la reconoce el automata, estoy haciendo algo mal o la solucion es incorrecta?

Saludos, gracias.

En respuesta a Fernando Andres Tomeo Lussich

Re: [Segundo parcial 2015] - Ejercicio 3, parte b.

de Diego Garat -

hola:

la tiras que planteás cumple las condiciones de Lb

   01011 = (01)20011 

p=2, m=1 y  t=0,  y cumplen p>m>0, t>=0


luego, si pertenece a Lb, es correcto que el autómata la acepte.


saludos,

d.-



En respuesta a Diego Garat

Re: [Segundo parcial 2015] - Ejercicio 3, parte b.

de Fernando Andres Tomeo Lussich -


Pero esa misma tira, se puede ver como : 01011 = (01)10112  en este caso la tira no pertenece al lenguaje pero si es reconocida por el automata.

Esa es mi duda, saludos.

En respuesta a Fernando Andres Tomeo Lussich

Re: [Segundo parcial 2015] - Ejercicio 3, parte b.

de Diego Garat -
hola:

la tira no puede pertenecer en un caso y dejar de pertenecer en otro a un lenguaje.  un elemento, o bien pertenece, o bien no pertenece a un conjunto dado. 

en una descripción por comprensión del conjunto se establece las condiciones que debe cumplir un elemento para estar en el conjunto, y en el caso de Lb, se debe leer como "existe una descomposición de la tira en tres partes, cada parte tiene cierta sintaxis y cierto largo". si la tira cumple ese requisito, que es un "existe", pertenece el lenguaje.

llevándolo a otro dominio, supongamos que defino el conjunto de los pares como P={ p / p=2*n,  n natural}

siguiendo el razonamiento original, el número 28 lo puedo escribir como 4*7 y luego no sería un elemento de P. sin embargo, existe OTRA descomposición de 28,  2*14, que cumple las condiciones impuestas; luego, 28 sí es un elemento de P, porque existe una descomposición de la forma requerida, aunque ciertamente haya otras descomposiciones que no la tengan.


saludos,
d.-