Edición de «Finales Virtuales Tleng: Marzo de 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.

== 01/03 ==

1) Si S es una GLC no Recursiva a izquierda. Entonces para todo par de no terminales A y B en S con <math> A \rightarrow_L B \alpha </math> una derivación más a la izquierda, la cantidad de pasos de derivación i está acotada por una constante c, es decir <math>i \leq  c </math>.

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

<math> A \rightarrow a </math>

<math> A \rightarrow BC </math>

<math> A \rightarrow BCD </math>

No se permiten  producciones <math> A \rightarrow B </math> 

donde A, B, C, D  son no terminales,  a es terminal. Entonces  son 3-Chomsky

<math>S \rightarrow ABC</math>  
 
<math> A \rightarrow BDE </math>

<math> A \rightarrow a </math>

<math> A \rightarrow BC </math>

<math> A \rightarrow BC </math>

No son 3-Chomsky

<math> A \rightarrow B </math>

<math> A \rightarrow ABCDE </math> tampoco es 3-Chmsky

<math> A \rightarrow abcedef </math> tampoco es 3-Chomsky

Dar un algoritmo que pase una gramatica libre de contexto a forma normal 3-Chomsky.

Dar la complejidad computacional.

== 04/03 ==

1) Dar un algoritmo que transforme cada gramatica libre de contexto G en otra G' que reconoce el mismo lenguaje pero es tal que si <math>X_1... X_k</math> es el lado derecho de una producción entonces
todos los símbos <math>X_1..X_k</math> son distintos.

Justificar la correctitud y  Dar la complejidad del algoritmo

Poner varios ejemplos

2) 
a) Determinar Verdadero o Falso y dar la demostración:

a- Para todo automata de pila no  deterministico existe otro deterministico   equivalente, es decir, que reconoce exactamente el mismo lenguaje.

b- Para todo automata de pila deterministico existe otro equivalente que siempre consume toda la entrada.

c- Si un lenguaje es libre de contexto su complemento también

b)
Determinar Verdadero o Falso y dar la demostración:

a- Para todo automata de pila no  deterministico existe otro deterministico   equivalente, es decir, que reconoce exactamente el mismo lenguaje.

b- Para todo automata de pila deterministico existe otro equivalente que siempre consume toda la entrada.

c- Si un lenguaje es libre de contexto su complemento también

3) Dar un algoritmo que transforme cada gramatica libre de contexto  G sin producciones A-> lambda en otra G' que reconoce el mismo lenguaje pero tal que  cada producción es de la forma A-> a alpha,
con a un símbolo terminal y alpha una cadena de no-terminales.

Justificar la correctitud y  Dar la complejidad del algoritmo

Poner ejemplos

Ayuda: pensar en el algoritmo de eliminiacion de la recursión