Automatas Finitos Deterministicos Y No Deterministicos

Automatas Finitos Deterministicos Y No Deterministicos

Las características de los autómatas finitos determinísticos son:

1. Un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre símbolos de entrada tomados de un alfabeto S .

2. Para cada símbolo de entrada existe exactamente una transición a partir de cada estado (posiblemente de regreso al mismo estado).

3. Un estado, por lo general denotado como q0 es el estado inicial, en el que el autómata comienza.

4. Algunos estados (tal vez ninguno) están designados como final o de aceptación. Un autómata finito determinístico es una quinta tupla (Q, S , d , q0, F) donde:

Q es un conjunto finito de estados.

S un alfabeto de entrada finito.

q0 elemento de Q , el estado inicial.

FÍ Q el conjunto de estados finales o de aceptación.

d es la función d : Q x S ® Q que determina el único estado siguiente para el par (q1, s ) correspondiente al estado actual q1 y la entrada s . Generalmente el término autómata finito determinístico se abrevia como DFA de sus siglas en inglés Deterministic Finite Automaton. Usaremos M = (Q, S , q0, F, d ) para indicar el conjunto de estados, el alfabeto, el estado inicial, el conjunto de estados finales y la función asociadas con el DFA M.

Se puede construir un diagrama para que ayude a determinar los distintos miembros o cadenas del lenguaje. Tal diagrama tiene la forma de un grafo dirigido con información añadida, y se llama diagrama de transición. Los nodos del grafo corresponden a los estados del DFA y se usan para señalar, en ese momento, hasta qué lugar se analizó la cadena.

Por lo general q0 es el estado inicial, marcando con una flecha (® ), el comienzo del autómata; algunos estados están designados como final o aceptación indicados por un doble círculo. Los símbolos del alfabeto son las etiquetas de los arcos del grafo. Si cuando ha sido tratada la cadena en su totalidad se termina en un estado de aceptación entonces la cadena es aceptada por el lenguaje. Si M es un AFD, entonces el lenguaje aceptado por M es L(M)={w Î S *½ w es aceptada por M}. Por tanto, L(M) es el conjunto de cadenas que hacen que M pase de su estado inicial a un estado de aceptación.

AUTÓMATAS FINITOS NO DETERMINÍSTICOS.

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 2Q es el conjunto de potencias de Q, el conjunto de todos los subconjuntos de Q). Obsérvese que puesto que d es una relación para todo par (q, s ) compuesto por el estado actual y el símbolo de la entrada, d (q, s ), es una colección de cero o más estados [es decir, d (q, s )Í Q]. Esto indica que, para todo estado q1 se pueden tener cero o más alternativas a elegir como estado siguiente, todas para el mismo símbolo de entrada.

Generalmente el término autómata finito no determinístico se abrevia como NFA de sus siglas en inglés Nondeterministic Finite Automaton. Si M es un NFA, definiremos el lenguaje acepatdo por M por medio de L(M)={w ½ w es una cadena aceptada por M} donde una cadena w es aceptada por M, si M pasa de su estado inicial a su estado de aceptación o final al recorrer w (w es consumida en su totalidad).


  • AUTOMATA FINITO DETERMINISTA***

Un Autómata Finito Determinista consiste en un dispositivo que puede estar en cualquier estado entre un número finito, uno de los cuales es el estado inicial y por lo menos uno es un estado de aceptación.

A este dispositivo está unido un flujo de entrada por medio del cual llegan en secuencia los símbolos de un alfabeto determinado.

La máquina tiene capacidad para detectar los símbolos conforme llegan y, basándose en el estado actual y el símbolo recibido, ejecutar una transición consistente en cambiar a otro estado o la permanencia en el mismo.

El programa de un Autómata Finito Determinista no debe contener ambigüedades (para un estado un determinado símbolo sólo puede producir una determinada acción).

Se dice que un Autómata Finito Determinista acepta su cadena de entrada si, después de comenzar sus cálculos en el estado inicial la máquina cambia a un estado de aceptación después de leer el último símbolo de la cadena.

Si después de leer el último símbolo no queda en estado de aceptación, se dice que la cadena ha sido rechazada. Si la entrada es una cadena vacía (l) será aceptada si y sólo si el estado inicial es también un estado de aceptación.

Un Autómata Finito Determinista consiste en una quíntupla ( S, S, d, i, F) donde:

• S, es un conjunto finito de estados. • S, es el alfabeto de la máquina. • d, es una función (función de transición) de S× S a S. • i, (un elemento de S) es el estado inicial. • F (un subconjunto de S) es el conjunto de estados de aceptación.

La interpretación de la función de transición d de un autómata finito determinista es que d(p,x)=q sí y sólo sí la máquina puede pasar de un estado p a un estado q al leer el símbolo x.

El diagrama de transición determinista sólo debe tener un arco que sale de un estado para cada símbolo del alfabeto. Además, dicho diagrama está completamente definido, es decir, debe existir un arco para cada símbolo del alfabeto.

  • AUTOMATA FINITO NO DETERMINISTA***

Esta maquina se parece mucho a un AFD, pues también analiza cadenas construidas a partir de un S y solo puede tener un numero finito de estados, algunos de los cuales son de aceptación y uno es el estado inicial.

A diferencia de los AFD, la transición que se ejecuta en una etapa dada de un AFN puede ser incierta, es posible aplicar cero, una o mas de una transición mediante el mismo símbolo de entrada, como sucede con una maquina que no esta completamente definida.

Un AFN acepta una cadena si es posible que su análisis deje a la maquina en un estado de aceptación.

De manera formal, un AFN se define como sigue, un AFN consiste en una quíntupla (S,∑ , p, i, F) donde:

• S es un conjunto finito de estados. • ∑ es el alfabeto de la maquina • p es un sub-conjunto de SXS XS llamada relación de transiciones. • i es le estado inicial (un elemento de S) • F es la colección de estados de aceptación (un sub-conjunto de S).


AUTOMATAS FINITOS DETERMINISTICOS


INTEGRANTES: Alicea Ramirez Ivan; Colmenero Jimenez Gustavo; Muñoz Aldaco Juan Carlos; Santiago de León Ronel Benjamín.

Un AFD o autómata finito determinista es aquel autómata finito cuyo estado de llegada está unívocamente determinado por el estado inicial y el carácter leído por el autómata.

Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representado con una 5-tupla (S,Σ,T,s,A) donde:

• Σ es un alfabeto

• S un conjunto de estados

• T es la función de transición:

• es el estado inicial

• es un conjunto de estados de aceptación o finales.

Al contrario de la definición de autómata finito, este es un caso particular donde no se permiten transiciones vacías, el dominio de la función T es S (con lo cual no se permiten transiciones desde un estado de un mismo símbolo a varios estados).

A partir de este autómata finito es posible hallar la expresión regular resolviendo un sistema de ecuaciones.

                S1 = 1 S1 + 0 S2 + ε

                S2 = 1 S2 + 0 S1

Siendo ε, la palabra nula. Resolviendo el sistema y haciendo uso de las reducciones apropiadas se obtiene la siguiente expresión regular: 1*(01*01*)*.

Inversamente, dada la expresión regular es posible generar un autómata que reconozca el lenguaje en cuestión utilizando el algoritmo de Thompson, desarrollado por Ken Thompson, uno de los principales creadores de UNIX, junto con Dennis Ritchie.


AUTOMATAS FINITOS NO DETERMINISTICOS


1). Un AFND o autómata finito no determinista es aquel que presenta cero, una o más transiciones por el mismo carácter del alfabeto.

Un autómata finito no determinista también puede o no tener más de un nodo inicial.

Los AFND también se representan formalmente como tuplas de 5 elementos (S,Σ,T,s,A). La única diferencia respecto al AFD es T.

AFD: T: S x Σ → S

AFND: T: S x Σ → P(S)(partes de S)

2). Un autómata finito no determinístico M es una quíntupla (X,Q,d,q0 , F/b), donde:

    * X es un conjunto no vacío que llamaremos alfabeto.
    * Q es un conjunto no vacío que llamaremos conjunto de estados.
    * d: Q x X® r (Q) es una Applet que llamaremos función de transiciones.
    * q0 Î Q es el estado inicial.
    * F Í Q es el conjunto de estados finales.
    * b: Q ® {0,1} es una Applet que llamaremos función de salida.

Extensión de d.

    * d*: Q x X* ®r(Q)
    * d*(q,L)= {q}
    * d*(q, wx) =È(d(q`,x)),q Î d*(q,w) con w Î X*, x Î X

Un AFN acepta una cadena w si, a medida que se leen los caracteres de w, es posible elegir en cada paso el estado siguiente de tal forma que partiendo del estado inicial sea posible llegar a un estado de aceptación. El hecho de que existan otras elecciones posibles que, siguiendo los símbolos de w, lleven a un estado que no es de aceptación o no lleven a ningún estado, no evita la aceptación de w por el AFN. Formalmente, dado un AFN, llamaremos lenguaje de M (denotado por L(M)) a: L(M) = { w Î X* / d* (q0 , w) Ç F ¹Æ } = { w Î X* / sup[r(b), d* (q0 ,w)] = 1}

Es decir, el lenguaje de N es el conjunto de las cadenas w que llevan al autómata desde el estado inicial a uno de los estados de aceptación.


(:includeurl http://docs.google.com/Present?docid=df8q8t4p_19d89k2dd8:)

VIDEO: Automata finito deterministico y no deterministico (:includeurl http://www.youtube.com/v/u7s8cCoAe-Y&hl=es&fs=1:)


Aqui empieza el trabajo de:

Perez Estrada Alejandro

Garcia Ortiz Pablo Ernesto

Perez Flores Salatiel

Reza Vitela Favian

Valadez Camacho Melissa

Uresti Muñoz Rodolfo

(:includeurl http://docs.google.com/Present?docid=df8jsr2j_10gsbsbvrm:)

(:includeurl http://docs.google.com/Present?docid=df8jsr2j_13cd4xv3cj:)


Mis sitios nuevos:
Emprendedores
Politica de Privacidad