search

PUC-IIC2223 / syllabus2019

Repositorio oficial para el curso "Teoría de Autómatas y Lenguajes Formales" del año 2019
3 stars 0 forks source link

I3 - Preguntas sobre el enunciado #41

Open crivero1 opened 4 years ago

crivero1 commented 4 years ago

P: Quería saber qué es el n en la P4 y a qué se refieren con el L^n. R: Se refiere a la concatenación de L n-veces. Formalmente, L^0 = {\epsilon}, L^n = {uv | u \in L^{n-1} y v \in L}.

P: En la P1, el "i · j" significa i multiplicado con j. R: Si.

P: Tengo una duda en la pregunta 2. Cuando nos piden demostrar la correctitud de nuestro algoritmo, si usamos el algoritmo CKY pero le agregamos algunas cosas, puedo suponer la correctitud del algoritmo CKY? R: Si, pueden asumir que el algoritmo CKY es correcto. Ahora, esto no necesariamente demostrará que su nuevo algoritmo es correcto.

nicovsj commented 4 years ago

P: Se puede asumir que todo lenguaje libre de contexto puede ser descrito equivalentemente por un autómata apilador? R: Si.

crivero1 commented 4 years ago

P: Cuando nos piden una derivación ¿se refieren a un árbol de derivación o a un subconjunto de producciones?

R: Se refiere a la secuencia de producciones.

crivero1 commented 4 years ago

P: En la P2, ¿cómo se debe retornar la derivación? R: Para la pregunta 2, la representación del output debe ser una derivación, lo que es equivalente a una secuencia de producciones. Por ejemplo, si la gramática es:

S -> B A A -> a B -> b

y la derivación es S => BA => bA => ba, entonces tu algoritmo podría representar la derivación como S->BA, B->b, A->a. Cualquier representación "razonable" de esta secuencia será considerado como correcto.

nicovsj commented 4 years ago

P: En la P3, pA->qBA implica agregar B al stack? R: Sí, justamente es eso.

crivero1 commented 4 years ago

P: Si en la P2 uso un método, por ejemplo "BuscarDerivación", que se encarga de entregar la derivación, ¿necesito definirlo o puedo describirlo a grandes rasgos?

R: Todos los métodos que usen en la pregunta 2 deben definirlos o explicarlos detalladamente. Debe quedar muy claro como obtienen y entregan la derivación desde su algoritmo.

crivero1 commented 4 years ago

P: En la P4, aun no me queda claro a que se refieren con L^n en la pregunta, ¿podrian explicar con más detalle?

R: La definición aparece en la Clase04, slide 7, del curso.