APLICACIONES Y EJEMPLOS DE AUTOMATAS Y MAQUINA DE TURNIG

APLICACIÓNES Y EJEMPLOS DE AUTOMATAS Y MAQUINA DE TURNIG
Autómatas Finitos (AF)
Los AF constituyen un modelo útil para muchos tipos importantes de hardware y software, como:

a) Software para el diseño y la verificación del comportamiento de circuitos digitales.

b) El “analizador léxico” de un compilador típico, esto es, la componente del compilador que
descompone el texto original enunidades lógicas tales como identificadores, palabras
reservadas y signos de puntuación.

c) Software para explorar grandes corpus de texto, como conjuntos de páginas web, o para
descubrir las apariciones de ciertas palabras, frases u otros patrones.

d) Software para comprobar la corrección de cualquier tipo de sistemas que tengan un
número finito de estados diferentes, como losprotocolos de comunicación o los protocolos
de intercambio seguro de información.

Los Autómatas Finitos (AF) son de dos tipos:
Deterministas (AFD):
•Cada combinación (estado, símbolo de entrada) produce un solo (estado)
No Deterministas (AFND):
•Cada combinación (estado, símbolo de entrada) produce varios estados (estado1, estado 2, …, estado i)
•Son posibles transiciones con λ.

Representación de unautómata finito determinista (AFD)
Un autómata finito determinista se puede representar mediante:

Diagramas de transición
tablas de transición

Diagramas de transición:

• nodos etiquetados por los estados (qi Q)
• arcos entre nodos qi a qj etiquetados con ei
(ei Σ ) si existe f(qi,ei) = qj
• q0 se señala con →
• qi F se señala con * o doble círculo

Tablas de transición:
 •Filas encabezadas porlos estados (qi Q)
•Columnas encabezadas por los símbolos de entrada (ei Σ )

Ejemplo de representación de autómata finito determinista (AFD)
Ejemplo: Sea el AFD1 = ({a,b}, {p,q,r}, f, p, {q}) donde f está
definida por:
f(p,a) = q f(p,b) = r
f(q,a) = q f(q,b) = r
f(r,a) = r f(r,b) = r
escribir su tabla de transición y dibujar su diagrama de transición

Para poder ingresar un autómata tendremosque ingresar la cantidad de símbolos y la cantidad de estados. Luego tendremos que ingresar los símbolos del alfabeto, los estados los genera solo no es necesario ingresarlo. Seguidamente tendremos que ingresar la matriz de transición donde no olvidemos que remplazamos los nombres de los estados por número que serian los índices.

Allí tenemos un ejemplo, donde s1 tomaría el valor de 0 y s2 el valorde 1y así tendríamos que ingresarlo en el programa cuando pida la matriz.

Seguidamente tenemos que indicar cuál es el estado inicial, supongamos que fuese S1entonces tendríamos que ingresar 1 ó 2 si fuese S2 lo mismo seria para los estados finales.

Verificar palabra: Es la parte donde probáramos nuestro autómata, tendremos que ingresarla de acuerdo a nuestro alfabeto de símbolos de ingresamosen la parte de "ingresar autómata".


Autómata con pila

Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A. Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos. Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control quepuede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como estado inicial, y además algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con elmanejo last-in-first-out (LIFO). Las transiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x.1

Al igual que un autómata finito un autómata de pila cuenta con...