TEORIA DE AUTOMATAS

LENGUAJES FORMALES

AUTOMATAS

1.Automatas Finitos
1.1.Concepto
1.2.Ejemplo de aplicabilidad 
1.3.Propuesta

2.Automatas Finitos Determinista
2.1.Concepto
2.2.Ejemplo de aplicabilidad 
2.3.Propuesta


1.  AUTOMATAS FINITOS:
 

Los autómatas finitos son máquinas formales que se usan para reconocer lenguajes regulares. Como se vio en el

capítulo anterior, estos son los lenguajes más sencillos, los lenguajes que son generados por gramáticas regulares.

En este capítulo se darán las definiciones formales de los autómatas determinísticos y los autómatas no determinísticos.

Adicionalmente, se muestra la relación entre estos y las expresiones regulares. Luego, se

describen los autómatas con respuestas y cómo estos pueden ser usados para hace traducciones o cálculos sencillos con las cadenas que pertenecen a los lenguajes regulares.

Finalmente, se habla de las limitaciones de este formalismo.

1.1 Qué es un autómata de estados finitos?

Un autómata de estados finitos es una máquina con un número finito de estados que lee símbolos de una cinta de

entrada infinita. El comportamiento de la máquina está determinado únicamente por el estado en que se encuentra y el símbolo en la cinta de entrada. Al leer un símbolo de la cinta de entrada cambia de estado y avanza en la cinta de entrada. Cuando ya no quedan símbolos por leer, para. Aún cuando la cita es infinita, la cadena que guía el comportamiento del autómata no lo es. Esta cadena puede ser tan larga como se quiera, pero siempre finita. 

1.2 El autómata de la figura describe el comportamiento de un semáforo peatonal. Inicialmente el semáforo está en rojo para el peatón y se supone que acaba de pasar a rojo. Se quiere garantizar que el semáforo permanezca en rojo al menos cuatro ticks

de reloj. Esto quiere decir que si el peatón oprime el botón y el semáforo acaba de pasar a rojo debe esperar cuatro ticks de reloj para que pase a amarillo (y luego a verde); si han pasado dos ticks sólo debe esperar dos ticks; y si han pasado 10 cambia inmediatamente.

Semaforo Peatonal

Oprimir el botón más de una vez no afecta el comportamiento. El semáforo permanece en verde por cuatro ticks de reloj.

1.3

2. AUTÓMATAS FINITOS DETERMINISTAS:


Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo.

2.2 •AFDeterministas, AFD’s: se definen mediante una quíntupla

(Σ, Q, f, q0, F), donde:

•Σ: alfabeto de entrada

•Q: conjunto de estados, es conjunto finito no vacío, realmente
un alfabeto para disDnguir a los estados

•f: QxΣ→Q, función de transición

•q0∈Q, estado inicial

•F⊂Q: conjunto de estados finales o de aceptación

2.3

 









BIBLIOGRAFIA

*http://www.uaeh.edu.mx/docencia/P_Presentaciones/huejutla/sistemas/lenguajes_automatas/afd.pdf
*http://sistemas.uniandes.edu.co/~isis1106/dokuwiki/lib/exe/fetch.php?media=bibliografia:capitulo3.pdf