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

De Cuba-Wiki
(Página creada con «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 s…»)
 
Sin resumen de edición
 
(No se muestran 2 ediciones intermedias 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

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[editar]

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»