Autómatas finitos deterministas

En esta página podremos encontrar información e imágenes acerca de lo autómatas finitos deterministas (AFD), para comenzar daremos una breve definición de lo que es un autómata finito determinista (AFD).

Autómata finito

Un autómata finito(AF) o máquina de estado finitoes un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida.
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 un autó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

automata finito determinista

automata finito determinista

  • Tablas de transición:

 •Filas encabezadas por los estados (qi Q)
•Columnas encabezadas por los símbolos de entrada (ei Σ )

automata finito determinista

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

automata finito determinista 2

Conceptos básicos de un autómata finito determinista (AFD)

  • Configuración: es un par ordenado de la forma (q,w) donde:

- q: estado actual del AF
– w: cadena que le queda por leer en ese instante, w Σ*
•Configuración inicial: (q0, t)
– q0: estado inicial
– t: cadena de entrada a reconocer por el AFD, t Σ*
•Configuración final: (qi,λ)
– qi: estado final
– λ la cadena de entrada ha sido leída completamente

  • Movimiento: es el tránsito entre dos configuraciones.

Autómata Finito Deterministas,  AFD: 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 distinguir a los estados
  • f: Q x Σ → Q, funciónde transición
  • q0, estado inicial
  • F c Q: conjunto de estados finales o de aceptación.

Autómatas finitos deterministas (AFD) como reconocedores del lenguaje

  • Autómata finito determinista (AFD) como reconocedor de un Lenguaje:

    • Cuando un AF transita desde q0a un estado final en varios movimientos, se ha producido el RECONOCIMIENTO o ACEPTACIÓN de la cadena de entrada
• Cuando un AF no es capaz de alcanzar un estado final, se dice que el Autómata finito NO RECONOCE la cadena de entrada y que ésta NO PERTENECE al lenguaje reconocido por el Automata finito

Equivalencia y miminización de autómatas finitos deterministas (AFD)

Es posible tener varios autómatas que reconozcan el mismo lenguaje.
– Para todo autómata se puede obtener un autómata equivalente(i.e. reconoce el mismolenguaje) donde el número de estados del autómata sea el mínimo.
– ¿Cuál sería el número mínimo de estados?
¿Porqué interesa obtener el mínimo?

Se dispone de un descriptor del lenguaje (lenguaje regular): gramática tipo 3, AFD, AFND, expresión regular

  • Se plantean problemas de decisión:

•¿El lenguaje descrito es vacio?
•¿Existe una determinada cadena w en el lenguaje descrito?
•¿Dos descripciones de un lenguaje describen realmente el mismo lenguaje?

  • Nota: usualmente los lenguajes son infinitos, con lo que no es posible plantear la pregunta y recorrer el conjunto INFINITO de cadenas.
  • Los algoritmos para responder a las dos primeras preguntas son sencillos. ¿Pero y para la última pregunta ?

¿Dos descripciones de un lenguaje describen realmente el mismo lenguaje?
Consecuencia de esta comprobación: Obtener el autómata finito determinista (AFD) mínimo equivalente.

Operaciones de minimización

- Eliminación de estados inaccesibles.

- Agrupación de estados equivalenteso indistinguibles.

Equivalencia de dos autómatas finitos deterministas (AFD)

Métodos para comprobar si 2 autómatas son equivalentes:

  • Algoritmo para comprobar la equivalencia de AFDs

- Se hace la suma directa de los dos AFD’s

- Se hace Q/E del AFD suma

- Si los dos estados iniciales están en la misma clase de equivalencia de Q/E los 2 AFD’s son equivalentes.

En los proximos días seguiremos dando información acerca de los autómatas finitos deterministas.

3 comentarios (+add yours?)

  1. Bienvenidos a nuestro nuevo blog « Automátas, gramáticas y lenguajes formales
    feb 29, 2012 @ 09:24:57

  2. luis
    mar 21, 2012 @ 13:25:36

    Está muy bien el blog, me pasaré en unos días para ver si teneis algo nuevo

    Responder

  3. Autómatas finitos deterministas y no deterministas « Automátas, gramáticas y lenguajes formales
    mar 26, 2012 @ 08:48:59

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: