desarrollo sustentable


Contenido


AUTÓMATAS
La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.
Un autómataes un modelo matemático para una máquina de estado finita (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla).(1)
AUTÓMATA FINITO DETERMINÍSTICO
El termino "determinista" hace referencia al hecho de que para cada entrada solo existe uno y sóloun estado al que el autómata pude hacer la transición a partir de su estado actual. Se utiliza la abreviatura "AFD", con el fin de recordar el tipo de  autómatas del que estamos hablando.(2)


DIAGRAMA DE TRANSICIONES

El término "autómata finito" hace referencia a la variedad determinista. Un autómata finito determinista  consta de: 
1. Un conjunto de estados: Q.
2. Un conjunto finito desímbolos de entrada.
3. Una función de transición que toma como argumento un estado y un símbolo de entrada y devuelve un estado.
4. Un estado inicial, uno de los estados de Q: q0.
5. Un conjunto de estados finales o de aceptación F. (3)

AUTÓMATA FINITO NO DETERMINÍSTICO
Los Autómatas Finitos No Deterministas, también llamados AFN, se caracterizan porque, a diferencia de los AFD, en un estadopuede haber más de una transición posible para un mismo símbolo de entrada (alfabeto). Es decir /λ(q,a)/ ≥ 1 para algún "q" perteneciente a Q y para algún símbolo "a" perteneciente a T.(4)
GRAMÁTICA DE CHOMSKY
En este libro Chomsky expone que una gramática de constituyentes inmediatos no es totalmente válida para explicar el mecanismo mediante el cual los hablantes de una lengua son capaces deproducir y entender oraciones. Podríamos definir el concepto de gramática como un conjunto de oraciones gramaticales. Chomsky objeta que existe un infinito número de oraciones en cada lengua por lo tanto tenemos que asumir que los seres humano están equipados con un mecanismo finito de conocimiento que les permite construir e interpretar un infinito número de oraciones. (5)

GRAMÁTICA DE LIBRECONTEXTO
son las que generan los lenguajes libres o independientes del contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico. Como toda gramática se definen mediante una cuádrupla G = (N, T, P, S), siendo
- N es un conjunto finito de símbolos no terminales
- T es un conjunto finito de símbolos terminalesN ∩ T = ∅
- P es un conjunto finito de producciones
- S es el símbolo distinguido o axioma S ∉ (N ∪ T) (6)

ÁRBOL DE DERIVACIÓN
Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje.



(7)
FUNCIONAMIENTO DE LA MAQUINA DE TURING
Es un dispositivo dereconocimientos de lenguaje, es más general que cualquier autómata finito y cualquier autómata de pila, debido a que ellas pueden reconocer tanto los lenguajes regulares, como los lenguajes independientes de contexto y además muchos otros tipos de lenguajes.
La máquina de Turing (abreviado MT) tiene, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente vienela palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el carácter blanco (que representaremos con “t”). La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el extremo izquierdo, la MT la cabeza lectora es de lectura y escritura, por lo que la cinta puede ser modificada en...