Edición de «Final del 17/09/10 (Teoría de Lenguajes)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
Línea 1: Línea 1:
{{Back|Teoría de Lenguajes}}
{{Back|Teoría de Lenguajes}}


1. (Escrito) Describir y demostrar la equivalencia entre AFND-L y AFND
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.


2. (Escrito) Demostrar que existe un lenguaje LIC que no es LICD
* Enunciar y demostrar pumping para lenguajes regulares.


3. (Escrito) Demostrar que todo LSC es recursivo
* 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?
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.


4. (Oral) Definir gramatica LR(k) (la definicion "nueva")
* 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).


[[Category:Finales]]
[[Category:Finales]]
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Final_del_17/09/10_(Teoría_de_Lenguajes)»