|
|
| Línea 1: |
Línea 1: |
| {{Back|Teoría de Lenguajes}} | | {{Back|Teoría de Lenguajes}} |
|
| |
|
| Todo oral, se puede usar pizarrón, los docentes ayudan si uno va por mal camino. Las demostraciones son a grandes rasgos, sin entrar en detalles de formalismo.
| | 1. (Escrito) Describir y demostrar la equivalencia entre AFND-L y AFND |
|
| |
|
| * Enunciar y demostrar pumping para lenguajes regulares.
| | 2. (Escrito) Demostrar que existe un lenguaje LIC que no es LICD |
|
| |
|
| * Se tiene un AFD al que se le conoce su alfabeto y la cantidad de estados n y se lo puede usar como una caja negra a la que le puedo pasar cadenas y retorna si la acepta o no. ¿Cuál es la longitud máxima de cadena que necesito pasarle para convencerme de que acepta o no cadenas infinitas?
| | 3. (Escrito) Demostrar que todo LSC es recursivo |
| Respuesta: con probar con todas las cadenas posibles de longitud hasta el doble de la cantidad de estados alcanza, ya que si encuentro una sola de longitud > n que es aceptada entonces acepta cadenas infinitas, pero si llego a probar todas las cadenas de hasta 2n y no encontré ninguna > n aceptada, entonces no acepta ninguna cadena infinita. El razonamiento es similar al usado para demostrar pumping.
| |
|
| |
|
| * Explicar cómo es tabla de LR y el algoritmo LR (en general para cualquier versión de LR, asumiendo que ya se tiene la tabla creada).
| | 4. (Oral) Definir gramatica LR(k) (la definicion "nueva") |
|
| |
|
| [[Category:Finales]] | | [[Category:Finales]] |
Revisión actual - 19:34 12 sep 2014
Plantilla:Back
1. (Escrito) Describir y demostrar la equivalencia entre AFND-L y AFND
2. (Escrito) Demostrar que existe un lenguaje LIC que no es LICD
3. (Escrito) Demostrar que todo LSC es recursivo
4. (Oral) Definir gramatica LR(k) (la definicion "nueva")
