1.Defina los siguientes conceptos

* Lenguaje: En Informática, los lenguajes de alto nivel son programas que traducen órdenes escritas en el lenguaje relativamente humano, al lenguaje de alto nivel (que es el que entiende el procesador).

 

* Automata: Equipo electrónico programable en lenguaje no informático y diseñado para controlar, en tiempo real y en ambiente industrial, procesos secuenciales.

 

* La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing.

 

* La complejidad computacional: es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. 

 

* Gramatica:

Una gramática ("G") desde el punto de vista de un autómata, es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman gramáticas equivalentes.

 

Una gramática es una estructura algebraica formada por cuatro elementos fundamentales:

 

G = { NT, T, S, P }

 

donde

    * NT es el conjunto de elementos No Terminales

    * T es el conjunto de elementos Terminales

    * S es el Símbolo inicial de la gramática

    * P es el conjunto de Reglas de Producción

 

* Conjunto es una Estructura de datos que consiste en una colección de elementos cuyo orden o cantidad de repeticiones no es observado. Es decir, { 1 2 3 } { 1 3 2 } { 1 2 1 2 3 } son el mismo conjunto.

 

* Inducción Matematica: La inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro n que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:

 

    Premisa mayor El número entero a tiene la propiedad P

    Premisa menor El hecho de que cualquier número entero n tenga la propiedad P implica que n + 1 también la tiene

    Conclusión Todos los números enteros a partir de a tienen la propiedad P.