Diferencia entre revisiones de «Finales Virtuales: Diciembre - Marzo»

De Cuba-Wiki
Sin resumen de edición
Sin resumen de edición
Línea 1: Línea 1:
Los finales virtuales consistieron de uno o dos ejercicios que le eran asignados a cada persona que rendia particularmente, abajo estan la lista de preguntas que se tomaron en las distintas fechas.
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 ==
== Septiembre ==
Línea 42: Línea 42:
4) Considerar la siguiente forma normal de 4-2-Chomsky donde todas las  producciones son  de la  forma
4) Considerar la siguiente forma normal de 4-2-Chomsky donde todas las  producciones son  de la  forma


A-->a
<math> A \rightarrow a </math>


A-->BCDE
<math> A \rightarrow BCDE </math>


A-->BC
<math> A \rightarrow BC </math>


donde A,B,C,D  son no terminales, a es terminal.  No se permiten  producciones A->B  ni A->BCE
donde A, B, C, D  son no terminales, a es terminal.   
 
No se permiten  producciones <math> A \rightarrow B </math> ni <math>A \rightarrow BCE </math>


Entonces  son 4-2-Chomsky
Entonces  son 4-2-Chomsky


S->ABCD
<math> S \rightarrow ABCD </math>


A->BDEF
<math> A \rightarrow BDEF </math>


A-> a
<math> A \rightarrow a </math>


A->BC
<math> A \rightarrow BC </math>


No son 4-2-Chomsky
No son 4-2-Chomsky


A->B
<math> A \rightarrow B </math>


A-> ABC  tampoco es 4-2-Chomsky
<math> A \rightarrow ABC </math> tampoco es 4-2-Chomsky


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


Dar un algoritmo que pasa una gramatica libre de contexto a forma normal de 4-2-Chomsky
Dar un algoritmo que pasa una gramatica libre de contexto a forma normal de 4-2-Chomsky
Línea 74: Línea 76:


5) Definir cuando una gramatica libre de contexto es recursiva a derecha.
5) Definir cuando una gramatica libre de contexto es recursiva a derecha.
Dar el algoritmo de eliminación de recursión a derecha (inmediata y no inmediata), su justificación de correctirud,   y su complejidad computacional.
Dar el algoritmo de eliminación de recursión a derecha (inmediata y no inmediata), su justificación de correctitud, y su complejidad computacional.


6) a) Consideremos un autómata finito determinístico con un contador, que es un valor  entero no negativo, que  el autómata solamente pude distinguir  entre cero y distinto de cero contadores.  El movimiento de la máquina contador depende de su estado,
6) a) Consideremos un autómata finito determinístico con un contador, que es un valor  entero no negativo, que  el autómata solamente pude distinguir  entre cero y distinto de cero contadores.  El movimiento de la máquina contador depende de su estado,
Línea 88: Línea 90:
(donde <math>N_0</math> son los naturales con el 0).
(donde <math>N_0</math> son los naturales con el 0).


Fijar  un conjunto de estados Q de 4 estados  y un alfabeto <math>\Sigma</math> de dos símbolos, valor máximo del contador M . Dar la cantidad de autómatas finitos determinísticos  de esta clase.
Fijar  un conjunto de estados Q de 4 estados  y un alfabeto <math>\Sigma</math> de dos símbolos, valor máximo del contador M. Dar la cantidad de autómatas finitos determinísticos  de esta clase.
 
b) Considerar un autómata finito determinístico con una pila donde:


b) Considerar  autómata finito determinístico  con una pila  donde
-  Solo hay dos símbolos de pila, <math>Z </math> y <math>X </math>.
-  Solo hay dos símbolos de pila, <math>Z </math> y <math>X </math>.
-  <math>Z</math> está inicialmente en la pila.
-  <math>Z</math> está inicialmente en la pila.
-  El autómata puede reemplazar <math>Z_0</math> solo por <math>X^i Z </math> para <math>i >= 0</math>
-  El autómata puede reemplazar <math>Z_0</math> solo por <math>X^i Z </math> para <math>i >= 0</math>
-  El autómata puede reemplazar <math>X</math> solo por <math>X^i</math> para i=0, 1, ó 2.
-  El autómata puede reemplazar <math>X</math> solo por <math>X^i</math> para i=0, 1, ó 2.
-  Es decir, Z aparece solo en la parte inferior de cada pila, y todos los demás símbolos de pila, si los hay, son X.
-  Es decir, Z aparece solo en la parte inferior de cada pila, y todos los demás símbolos de pila, si los hay, son X.


Línea 103: Línea 110:
== Marzo ==
== 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 <= c.
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 <math>i \leq  c </math>.


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


A-->a
<math> A \rightarrow a </math>


A-->BC
<math> A \rightarrow BC </math>


A-->BCD
<math> A \rightarrow BCD </math>


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


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


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


A-> a
<math> A \rightarrow BC </math>


A->BC
<math> A \rightarrow BC </math>


No son 3-Chomsky
No son 3-Chomsky


A->B
<math> A \rightarrow B </math>


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


A-> abcedef  tampoco es 3-Chomsky
<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 un algoritmo que pase una gramatica libre de contexto a forma normal 3-Chomsky.
Línea 138: Línea 147:


2)  
2)  
a)Determinar Verdadero o Falso y dar la demostración:
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.
a- Para todo automata de pila no  deterministico existe otro deterministico  equivalente, es decir, que reconoce exactamente el mismo lenguaje.

Revisión del 22:30 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)Consideremos el transductor finito dado por una máquina de Mealy Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (S, S_0, \Sigma, \Gamma, T, G)} que consiste de lo siguiente:

S es un conjunto finito de estados.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S_0 } es un estado inicial

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma } es el alfabeto de entrada

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Gamma } es el alfabeto de salida

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta }  : S Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \times \Sigma \to S } es la función de transición

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \gamma: S\times \Sigma \to \Gamma } mapea un estado y un símbolo de entarda a un símbolo de salida.

Definir la relación de equivalencia de estados usado en para el algoritmo de minimizacion considerando la función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta } extendida y la función gamma extendida.

b) Demostrar que para todo autómata de pila determinístico P = Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (Q, \Sigma, \gamma, \delta, q_0, Z_0, F) } 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

Diciembre

1) Dar el algoritmo de minimizacion de autómatas finitos deterministicos, la demostracion de correctitud y su complejidad computacional.

2) Fijados los alfabetos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Gamma} , ¿Cuántos autómatas de pila distintos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (Q, \Sigma, \delta, \Gamma, q_0, F)} determinístiscos hay, Si Q tiene 5 estados y en cada transición se escriben en la pila 0, 1 o 2 símbolos? ¿Y cuántos no determinísticos?

3) Demostrar que dada una gramática regular a derecha se puede obtener una gramática regular a izquierda equivalente. Tener en cuenta que disponemos del algoritmo para ir de gramática regular a derecha a autómata finito y que también disponemos del algoritmo para ir de autómata finito a gramática regular a derecha.

Hint: hallar la gramática del reverso de un lenguaje y el autómata finito del reverso de un lenguaje, o sea, dada G tal que L=L(G) hallar GR tal que LR=L(GR) y dado M tal que L=L(M) hallar MR tal que LR=L(MR), donde LR es el reverso del lenguaje L. Ayuda adicional: Hacer un ejemplo de gramática con 2 no terminales y 2 terminales y que genere una sola cadena.

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

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow a }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BCDE }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BC }

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

No se permiten producciones Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow B } ni Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BCE }

Entonces son 4-2-Chomsky

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S \rightarrow ABCD }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BDEF }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow a }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BC }

No son 4-2-Chomsky

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow B }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow ABC } tampoco es 4-2-Chomsky

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow abcedef } tampoco es 4-2-Chomsky

Dar un algoritmo que pasa una gramatica libre de contexto a forma normal de 4-2-Chomsky Justificar correctitud.

Dar la complejidad computacional

5) Definir cuando una gramatica libre de contexto es recursiva a derecha. Dar el algoritmo de eliminación de recursión a derecha (inmediata y no inmediata), su justificación de correctitud, y su complejidad computacional.

6) a) Consideremos un autómata finito determinístico con un contador, que es un valor entero no negativo, que el autómata solamente pude distinguir entre cero y distinto de cero contadores. El movimiento de la máquina contador depende de su estado, símbolo de entrada y de si su contador es cero. En un movimiento la máquina contador puede: (a) Cambiar de estado. (b) Sumar o restar 1 a su contador.

Sin embargo, un contador no puede volverse negativo, por lo que no puede restar 1 de un contador que actualmente es 0.

El autómata es la tupla Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (Q, \Sigma, \delta, q_0, F)} ,

donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta: Q\times Sigma \times N_0 \rightarrow Q} (donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle N_0} son los naturales con el 0).

Fijar un conjunto de estados Q de 4 estados y un alfabeto Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma} de dos símbolos, valor máximo del contador M. Dar la cantidad de autómatas finitos determinísticos de esta clase.

b) Considerar un autómata finito determinístico con una pila donde:

- Solo hay dos símbolos de pila, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Z } y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle X } .

- Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Z} está inicialmente en la pila.

- El autómata puede reemplazar Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Z_0} solo por Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle X^i Z } para Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle i >= 0}

- El autómata puede reemplazar Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle X} solo por Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle X^i} para i=0, 1, ó 2.

- Es decir, Z aparece solo en la parte inferior de cada pila, y todos los demás símbolos de pila, si los hay, son X.

Formalizar el autómata P como una tupla Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (Q, \Sigma, \Gamma, \delta, q_0, F)} explicitando la función de transición delta.

Fijar un conjunto de estados Q de 4 estados y un alfabeto Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma} de dos símbolos, dar la cantidad de autómatas finitos deterministicos de esta clase.

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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle i \leq c } .

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

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow a }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BC }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BCD }

No se permiten producciones Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow B }

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

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S \rightarrow ABC}

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BDE }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow a }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BC }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow BC }

No son 3-Chomsky

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow B }

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow ABCDE } tampoco es 3-Chmsky

tampoco es 3-Chomsky

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

Dar la complejidad computacional.

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

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Finales_Virtuales:_Diciembre_-_Marzo&oldid=13516»