FTI - SPDP

Todos los lenguajes independientes del contexto pueden ser aceptados por autómatas de pila no deterministas, y por autómatas de pila deterministas. Verdadero. Falso.

Las proyecciones, composición y recursividad primitiva, son ejemplos concretos de técnicas de construcción de funciones y producen funciones totales cuando se aplican a funciones totales. Verdadero. Falso.

(g*f)(X) = g(f(X)) donde X es K-TUPLA. Verdadero. Falso.

Si la complejidad temporal de una máquina de Turing es n, entonces la complejidad espacial, debe ser mayor que n. Verdadero. Falso.

La función es Ackermann es computable de N a N, es total, y recursiva primitiva. Verdadero. Falso.

Existen lenguajes que no son recursivamente enumerables. Verdadero. Falso.

El reconocimiento de lenguajes independientes del contexto mediante autómatas de pila, asegura la ejecución de una sucesión finita de transiciones, al definir si una palabra determinada es aceptada o no, por lo que se desarrolla con eficiencia. Verdadero. Falso.

Análisis lexicográfico.

Análisis sintáctico.

Análisis semántico.

Toda función ambigua no es LR. Verdadero. Falso.

Función cero, función sucesor, función proyección. Funciones iniciales. Funciones recursivas primitivas. Funciones μ-recursivas. Funciones computables.

"Establece una correspondencia entre la cero tupla y el cero". Función cero. Función sucesor. Función proyección.

"Suma 1 a su valor de entrada". Función cero. Función sucesor. Función proyección.

"Extrae como salida un componente específico de una tupla de entrada". Función cero. Función sucesor. Función proyección.

Combinación de dos funciones, composición de dos funciones, recursividad primitiva. Funciones iniciales. Recursividad. Técnicas de construcción de funciones. Funciones finales.

Las técnicas de construcción observadas producen funciones totales cuando se aplican a funciones totales. Verdadero. Falso.

Las funciones iniciales son funciones totales. Verdadero. Falso.

La clase de las funciones totales computables se conoce como clase de las funciones μ-recursivas. Verdadero. Falso.

La minimización puede puede producir funciones que no están definidas para ciertas entradas. Verdadero. Falso.

Las 4 nociones básicas de la asignatura... Gramática. Lenguajes. Problemas. Autómatas. MT. Complejidad computacional. Funciones iniciales. Gramáticas recursivas enumerables.

Gramática regular. Lado izquierdo formado por un único No Terminal. Lado derecho formado por un terminal concatenado con un No Terminal, un terminal o la cadena nula. Genera lenguaje regular. Se corresponde a un AF determinista. Lado derecho no tiene restricción, tiene una cadena de no terminales y terminales “concatenados”. Se corresponde a un AP no determinista.

Gramática independiente del contexto. Lado izquierdo formado por un único No Terminal. Lado derecho formado por un terminal concatenado con un No Terminal, un terminal o la cadena nula. Genera lenguaje regular. Se corresponde a un AF determinista. Lado derecho no tiene restricción, tiene una cadena de no terminales y terminales “concatenados”. Genera un lenguaje independiente del contexto. Se corresponde a un AP no determinista.

Gramática sensible al contexto. Lado izquierdo formado por un único No Terminal. Se corresponde a un AP no determinista. Genera un lenguaje decidible por MT o recursivo. Lado izquierdo puede tener varios terminales y no terminales “concatenados”. Lado derecho puede tener varios símbolos terminales y no terminales concatenados. El lado izquierdo puede ser menor o igual al lado derecho pero nunca mayor. Se corresponde a un MT No determinista o linealmente acotado.

Gramática irrestricta. Lenguaje correspondido: Recursivamente Enumerables y no Recursivos. Se corresponde a un AP no determinista. Relacionado al conjunto de Problemas Computables. Lado izquierdo puede tener varios terminales y no terminales “concatenados”. Se corresponde con MT. El lado izquierdo puede ser menor o igual al lado derecho pero nunca mayor. Lado izquierdo y derecho pueden contener símbolos terminales o no terminales o solo no terminales.

Las formas normales son solo para gramáticas independientes del contexto. Verdadero. Falso.