Finales Virtuales Tleng: Marzo de 2020

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.

Marzo

1) Si S es una GLC no Recursiva a izquierda. Entonces para toda producción A y B en S con A => Bα, la cantidad de pasos de derivación i está acotada por una constance c, es decir $i\leq c$.

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

$A\rightarrow a$

$A\rightarrow BC$

$A\rightarrow BCD$

No se permiten producciones $A\rightarrow B$

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

$S\rightarrow ABC$

$A\rightarrow BDE$

$A\rightarrow a$

$A\rightarrow BC$

$A\rightarrow BC$

No son 3-Chomsky

$A\rightarrow B$

$A\rightarrow ABCDE$ tampoco es 3-Chmsky

$A\rightarrow abcedef$ tampoco es 3-Chomsky

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

Dar la complejidad computacional.

3) Dar un algoritmo que transforme cada gramatica libre de contexto G en otra G' que reconoce el mismo lenguaje pero es tal que si $X_{1}...X_{k}$ es el lado derecho de una producción entonces todos los símbos $X_{1}..X_{k}$ son distintos.

Justificar la correctitud y Dar la complejidad del algoritmo

Poner varios ejemplos

4) 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