Tipos de autómatas

laDIFERENCIA ENTRE AUTOMATA FINITO Y AUTOMATA FINITO NO DETERMINISTICO
AUTOMATA FINITO
E un modelo matemático de una maquina que acepta cadenas de un lenguaje definido sobre un alfabeto A.Consiste en un conjunto finito de estados y uno de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada.
El Autómata finito acepta una cadena x si la secuencia detransiciones correspondientes a los
Símbolos de x conduce desde el estado inicial a un estado final.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a loslenguajes formales más simples según la Jerarquía de Chomsky.
En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajesformales. Esta jerarquía fue descrita por Noam Chomsky en 1956.
La Jerarquía de Chomsky consta de cuatro niveles:
* Gramáticas de tipo 0 (sin restricciones
* Gramáticas de tipo 1 (gramáticassensibles al contexto) generan los lenguajes sensibles al contexto.
* Gramáticas de tipo 2 (gramáticas libres del contexto) generan los lenguajes independientes del contexto.
* Gramáticas de tipo 3(gramáticas regulares) generan los lenguajes regulares. Estas gramáticas se restringen a aquellas reglas que tienen en la parte izquierda un no terminal, y en la parte derecha un solo terminal,posiblemente seguido de un no terminal. La regla también está permitida si S no aparece en la parte derecha de ninguna regla. Estos lenguajes son aquellos que pueden ser aceptados por un autómata finito.También esta familia de lenguajes pueden ser obtenidas por medio de expresiones regulares.

AUTOMATA FINITO NO DETERMINISTICO
Un autómata finito no determinístico es una quinta tupla ( Q, S , q0, d ,F) en donde Q, S , q0 y F (estados, entradas, estado inicial y estados finales) poseen el mismo significado que para un DFA, pero en este caso d es una transformación de Q x S a 2Q. (Recuérdese que...