Diferencia entre revisiones de «Finales Virtuales Tleng: Septiembre de 2020»

De Cuba-Wiki
Sin resumen de edición
Sin resumen de edición
 
(No se muestra una edición intermedia del mismo usuario)
Línea 3: Línea 3:
== Septiembre ==
== Septiembre ==


1)  
1) a) Dar un algoritmo que determine si un lenguaje regular dado es infinito.  Dar la complejidad del algoritmo y justificar.


a) Consideremos el transductor finito dado por una máquina de Mealy
b) Sea GA1 una gramática de atributos bien definida.
<math>(S, S_0, \Sigma, \Gamma, T, G)</math>
Demostrar que  es posible obtener una gramática de atributos GA2, equivalente a GA1, tal que GA2 no contiene atributos heredados.
que consiste de lo siguiente:


S es un conjunto finito de estados.
2) a)
Considerar la siguiente forma normal de 3-Chomsky donde todas las  producciones son  de la  forma


<math>S_0 </math> es un estado inicial
<math> A \rightarrow a </math>


<math>\Sigma </math> es el alfabeto de entrada
<math> A \rightarrow BC </math>


<math> \Gamma </math> es el alfabeto de salida
<math> A \rightarrow BCD </math>


<math> \delta </math> : S <math> \times \Sigma \to S </math> es la función de transición
donde A, B, C, D  son no terminales,  a es terminal.


<math> \gamma: S\times \Sigma \to \Gamma </math>
Dar un algoritmo que transforma una gramática libre de contexto <math> G=(V,N,P,S) </math> sin producciones lambda a forma normal 3-Chomksy.
mapea un estado y un símbolo de entarda a un símbolo de salida.
Justificar la correctitud.
Dar la complejidad computacional de este algoritmo.


Definir la  relación de equivalencia de estados usado en para el algoritmo de minimizacion considerando la función <math>\delta </math> extendida y la función gamma extendida.
b)
 
Demostrar que, para todo k, toda gramática LR(k) no es ambigua
b) Demostrar que para todo autómata de pila determinístico  P = <math> (Q, \Sigma, \gamma, \delta, q_0,  Z_0, F) </math> hay otro P′ tal que L(P) = L(P′) y P′ no tiene configuraciones que ciclen.
 
Ayuda: Dar primero la definición de configuración que cicla
 
2) a) Dar un ejemplo de un lenguaje regular y una cadena w en el lenguaje  y la aplicacion del lema de Pumping para lenguajes regulares,  para la cual haya mas de una  forma de factorizar la cadena, es decir que bombee dos veces.
 
b) Dar el automata finito para las prefijos viables de LR(1)
Explicar por qué es deterministico

Revisión actual - 23:02 4 mar 2021

Los finales virtuales consistieron de uno o dos ejercicios escritos que le eran asignados a cada persona que rendia particularmente, abajo estan la lista de preguntas que se tomaron en las distintas fechas.

Septiembre

1) a) Dar un algoritmo que determine si un lenguaje regular dado es infinito. Dar la complejidad del algoritmo y justificar.

b) Sea GA1 una gramática de atributos bien definida. Demostrar que es posible obtener una gramática de atributos GA2, equivalente a GA1, tal que GA2 no contiene atributos heredados.

2) a) Considerar la siguiente forma normal de 3-Chomsky donde todas las producciones son de la forma

donde A, B, C, D son no terminales, a es terminal.

Dar un algoritmo que transforma una gramática libre de contexto sin producciones lambda a forma normal 3-Chomksy. Justificar la correctitud. Dar la complejidad computacional de este algoritmo.

b) Demostrar que, para todo k, toda gramática LR(k) no es ambigua

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Finales_Virtuales_Tleng:_Septiembre_de_2020&oldid=13539»