Buenas, algún alma bondadosa que lo suba? No le saqué copia.

muchas gracias!

Acá va, gracias a todos los que no lo subieron =)

Gracias por subirlo!
Tenés alguna idea de cómo resolver el primero?
Ayer estuve mirando el cuaderno y hay dos lenguajes que aparecen en el ejercicio y en el cuaderno; uno como LIC para ejemplificar un AFPD y otro en el capítulo de MT para ejemplificar un lenguaje que no sea LR ni LIC. Los dos lenguajes son: (a^n b^n) y (a^n b^n c^n).

El resto de los lenguajes no sabría como justificarlo.
Saludos!

Yo me guié por el libro viejo (el de antes que existan éstos 3 volumenes, consideremos que yo la cursé en 2008) que decía que si hay 2 caracteres que están elevados a la misma potencia, entonces no se puede reconocer con AF, sí con AP porque la pila ayuda a contar y descontar los caracteres para saber si está ok la cantidad, como ejemplo el caso que vos decís de a y b elevados ambos a la "n". Fijate que hay desarrollados en el volumen 2 ejemplos que muestran como hace eso el AP.

Pero si son más de 2, tampoco puede ser con la pila, entonces es MT como está claro en el primer caso (que además es el que figura en la explicación del libro).

Con saber eso en éste caso alcanzaba me parece

este final es mucho mas complicado que el que tomaron la semana pasada :/

como te fue maru?

Interesante. Mirá vos que bien, una lástima que no esté en el libro nuevo. Pero bueno...
Gracias por responder!

De nada Chocolito! al fin algo que puedo responder en ésta materia jajaja

(14-12-2011 16:17)tebb escribió:  este final es mucho mas complicado que el que tomaron la semana pasada :/

creo que pasa siempre en SSL, si uno fue accesible, el siguiente va de complicado a "masacrante"

escuché a varios antes de rendir "hoy para mí va estar complicado porque la semana pasada fue fácil" (o frases similares)

(14-12-2011 15:20)Chocolito escribió:  Gracias por subirlo!
Tenés alguna idea de cómo resolver el primero?
Ayer estuve mirando el cuaderno y hay dos lenguajes que aparecen en el ejercicio y en el cuaderno; uno como LIC para ejemplificar un AFPD y otro en el capítulo de MT para ejemplificar un lenguaje que no sea LR ni LIC. Los dos lenguajes son: (a^n b^n) y (a^n b^n c^n).

El resto de los lenguajes no sabría como justificarlo.
Saludos!

L1: No podés con un AFD normal porque no tenés forma de contar que un caracter se repita la misma cantidad de veces que otro. Tampoco con un AFPD porque usa el siguiente procedimiento para contar:
por cada "a" que aparece mete un símbolo en la pila, y después cuando vienen las "b" va sacando lo que puso, sabe que hay la misma cantidad de bes porque saca todo lo que metió, el tema es que cuando viene una "c" ya la pila la tiene vacía, así que no tiene forma de "recordar" n. Es decir, con el autómata de pila sólo podés fijarte que dos letras tengan la misma cantidad, más no. Nota para recordar: AFD puede reconocer LRs, AFPD puede reconocer LRs y la mayoría de los LICs y la MT puede reconocer cualquier lenguaje formal

L2: Como no es LR no va AFD. El AFPD sí puede, porque mete simbolos cuando aparecen las aes, los saca cuando aparecen las bes y después vuelve a hacer lo mismo con a y z (son dos "cuentas" diferentes)

L3: Es LR, la ER sería a*bbb*

L4: Es finito => puede ser generado por una GR => es LR => puede ser reconocido por el AFD, AFPD y MT.

L5: No es LR. El AFPD puede porque sólo tiene que "llevar una cuenta", que es que las dos cantidades de aes sean iguales.

Anirus, muy buena y completa tu respuesta. Una consulta sobre la afirmación que haces. Vos decís:

"Nota para recordar: AFD puede reconocer LRs, AFPD puede reconocer LRs y la mayoría de los LICs y la MT puede reconocer cualquier lenguaje formal"

¿Ese "y la mayoría de los LICs" como se fundamenta?. ¿Que LIC's reconoce y cuales no?

Gracias!

Con un contraejemplo

Un AFPD no puede reconocer todos los LICS, pero un AFPND si.
Está en el Vol II

(16-12-2011 00:08)gonnza escribió:  Con un contraejemplo

Un AFPD no puede reconocer todos los LICS, pero un AFPND si.
Está en el Vol II

¿Por qué? No entiendo eso... Si podes darme un ejemplo o algo que me aclare más te agradecería, porque miro la página 29 del VOLII y no veo nada al respecto.

Ya que estamos con Autómatas (por si alguien lo sabe) en el final del 22/09/2011 una afirmación dice:
"En los AFDR se pueden hacer transiciones sin meter un símbolo en la pila"
¿Qué autómatas son los AFDR? No vi esa denominación en ninguna parte...


Muchas gracias!

(16-12-2011 01:42)Ident escribió:  

(16-12-2011 00:08)gonnza escribió:  Con un contraejemplo

Un AFPD no puede reconocer todos los LICS, pero un AFPND si.
Está en el Vol II

¿Por qué? No entiendo eso... Si podes darme un ejemplo o algo que me aclare más te agradecería, porque miro la página 29 del VOLII y no veo nada al respecto.

Ya que estamos con Autómatas (por si alguien lo sabe) en el final del 22/09/2011 una afirmación dice:
"En los AFDR se pueden hacer transiciones sin meter un símbolo en la pila"
¿Qué autómatas son los AFDR? No vi esa denominación en ninguna parte...


Muchas gracias!

Lo del AFPD y AFPND está en la página 27, después del ejemplo/ejercicio 2(no me había dado cuenta de que hablaba de determinísticos, creí que se refería a todos), respecto al AFDR google y dice autómata finito descendente recursivo, no lo recuerdo

Muchas gracias, por la consulta de AFPD y AFPDN está claro en ese fragmento de la pág.27. Ahora, lo de AFDR la verdad no me suena para nada. Me fijaré más tranquilo en algunas páginas del Vol II que todavía no vi, quizá en algún fragmento de una página aparezca...

(16-12-2011 02:19)Ident escribió:  Muchas gracias, por la consulta de AFPD y AFPDN está claro en ese fragmento de la pág.27. Ahora, lo de AFDR la verdad no me suena para nada. Me fijaré más tranquilo en algunas páginas del Vol II que todavía no vi, quizá en algún fragmento de una página aparezca...

Capaz era AFDP y le pifiaron a la letra. O le pusieron AFDR para que digas que es falso porque no existe ese tipo de autómata, como hicieron con el "módulo semántico" en una ocasión.

Respecto de "Un AFPD no puede reconocer todos los LICS, pero un AFPND si." lo dice al principio cuando indica que un autómata de pila en realidad es un dispositivo no determinístico y que los determinísticos reconocen solo una parte de los LICS. Ni idea la página...