Chomsky

EXPOSICION SOBRE LA GRAMATICA DE CHOMSKY

Definiciones de autómata:
• Autómata, del latín automăta y este del griego automatos (αὐτόματος), espontáneo o con movimiento propio. Según la RAE,máquina que imita la figura y los movimientos de un ser animado.
• Dispositivo o conjunto de reglas que realizan un encadenamiento automático y continuo de operaciones capaces de procesar una información deentrada para producir otra de salida.

El autómata es la primera máquina con lenguaje, es decir, un calculador lógico cuyo juego de instrucciones se orienta hacia los sistemas de evoluciónsecuencial.

TEORIA
En la Teoría de los lenguajes formales, disciplina perteneciente a la informática, se describen tres tipos de autómatas que reconocen tipos diferentes de lenguajes: los autómatasfinitos, los autómatas a pila y las máquinas de Turing.

AUTOMATA FINITO: Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida porsímbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.

AUTOMATA DE PILA: Un autómata con pila o autómata a pila es un modelo matemático de un sistema que recibeuna cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata a pila pertenece al grupo de loslenguajes de contexto libre en la clasificación de la Jerarquía de Chomsky.

MAQUINA DE TURING: La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computablenumbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas sondecidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador,...