Autómatas Finitos Unidad 3 Ante Chávez Pedro Edwin. No. de control: 10400336 Carrera: "I.S.C."

Solve your problems or get new ideas with basic brainstorming

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Autómatas Finitos Unidad 3 Ante Chávez Pedro Edwin. No. de control: 10400336 Carrera: "I.S.C." por Mind Map: Autómatas Finitos  Unidad 3 Ante Chávez Pedro Edwin. No. de control: 10400336 Carrera: "I.S.C."

1. ESTADOS INACCESIBLES

1.1. Sea M=(Q,Σ,δ,q0,F) un AFD. Un estado q∈Q decimos que es inaccesible, si no existe ninguna palabra sobre el alfabeto de entrada que partiendo desde q0 llegue a q. Con símbolos será q inaccesible si δ(q ,ω) q ˆ ω , * ∀ ∈Σ 0 ≠ Los estados que no son inaccesibles decimos que son accesibles. Si eliminamos los estados inaccesibles y todas sus transiciones el AFD obtenido es equivalente al dado. 2. Autómatas Finitos 2.1 Autómatas Finitos Deterministas (AFD) © Inmaculada Luengo 25 Ejemplo: En el AFD M3 de la figura, el estado r es inaccesible por que no se puede alcanzar a partir del estado inicial

2. Ejemplos de un ADF:

2.1. La máquina M1 del ejemplo se representa con una tabla δ a b →p q r q p q *r r r Tabla 2.2. Autómata finito determinista M1.

2.2. DIAGRAMA

3. LENGUAJE ACEPTADO POR UN AFD.

3.1. Es el conjunto de todas las palabras aceptadas, es decir: L( ) M {ω : δ ˆ (q ,ω) F} * = ∈Σ 0 ∈

3.2. Ejemplos: El lenguaje de M2 son todas las cadenas de ceros y unos que empiezan por cero y tiene al menos un uno ( ) { } * L M = x1 y :x,y∈Σ

4. Definición

4.1. Es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.

4.2. es la siguiente: Un autómata finito es un vector de tres elementos M = (I,S,δ, F) donde I es el conjunto finito de entradas, S es el conjunto finito de estados (no vacío), δ es la función de transición de estados y F es el conjunto finito de estados finales (incluidos en S).

4.2.1. 1

4.3. Un autómata finito determinista es una quíntupla que denotaremos de manera genérica por M=(Q,Σ,q0,δ,F) donde: Q es un conjunto finito cuyos elementos llamaremos estados. Σ es un alfabeto que llamamos alfabeto de entrada. q0 ∈Q es un estado señalado que llamamos estado inicial. F es un subconjunto de Q no vacío, cuyos elementos llamamos estados finales. δ es una aplicación de Q×Σ→Q , que llamamos función de transición.

5. PALABRA ACEPTADA POR UN AFD.

5.1. Decimos que ω∈Σ* es una palabra aceptada por el autómata finito determinista M si desde el estado inicial entrando consecutivamente de izquierda a derecha los símbolos

5.2. de la palabra en cuestión, se alcanza un estado final. Expresado con símbolos si ( ) F ω , q δˆ ∈ 0 .

5.3. Ejemplos: Las cadenas abb, baa, b, abbaaa son palabras aceptadas por M1. Las cadenas 01, 0001, 001001 son palabras aceptadas por M2.

6. Representación de un ADF

6.1. Con una tabla: Se ponen tantas filas como estados, y tantas columnas como símbolos forman el alfabeto. Marcamos el estado inicial con una flecha de entrada y cada uno de los estados finales con un asterisco. En el cruce de la fila marcada con el estado q y la columna marcada con el símbolo a del alfabeto ponemos el estado δ(q,a).

6.2. Con un diagrama: Cada estado no final se representa con un círculo; cada estado final se representa con un doble círculo; se señala el estado inicial con una flecha entrando, sin etiqueta; por cada transición δ(q,a)=t se dibuja una flecha dirigida del estado de partida q al de llegada llegada t etiquetada a

7. AUTÓMATA CONEXO.

7.1. Un AFD decimos que es conexo si no tiene estados inaccesibles. Si un AFD no es conexo basta eliminar los estados inaccesibles y todas sus transiciones (las de entrada y las de salida) para obtener un nuevo AFD conexo equivalente al de partida.

7.2. Ejemplo: El AFD M4 obtenido quitando a M3 el estado r y sus transiciones, es conexo

8. EQUIVALENCIA DE AFDS

8.1. Sean M y M′ dos AFDs, decimos que son equivalentes si L(M)=L(M`). Según lo que hemos dicho hasta el momento los AFDs se caracterizan por las palabras que aceptan y es menos importante la estructura interna de la máquina, el número de 2. Autómatas Finitos 2.1 Autómatas Finitos Deterministas (AFD) © Inmaculada Luengo 24 estados, cuántos estados finales tenga, etc… Digamos que un AFD es principalmente una especie de filtro de todas las cadenas posibles sobre el alfabeto de entrada. Los AFDs tienen muchas utilidades, en particular a nosotros nos interesa especialmente su utilidad como analizadores léxicos. Cuando, por ejemplo, en un programa necesitamos una expresión algebraica del tipo (a+b)*c/(d+e) debe estar correctamente escrita y de comprobarlo se encarga precisamente un analizador construido a partir de un autómata. Lo más normal es que tengamos un lenguaje de interés L sobre un alfabeto Σ y construyamos un AFD cuyo lenguaje sea precisamente L.

8.2. Construir un AFD sobre el alfabeto Σ={0,1} cuyo lenguaje sea L={cadenas que terminan en 00}

9. LENGUAJE ACEPTADO POR UN AFD.

9.1. Es el conjunto de todas las palabras aceptadas, es decir: ( ) ( ) { } F ω , q δˆ L M = ω∈Σ* : ∈ 0 Ejemplos: El lenguaje de M2 son todas las cadenas de ceros y unos que empiezan por cero y tiene al menos un uno L(M) = {x1y : x, y ∈Σ* }

10. EQUIVALENCIA DE AFDS.

10.1. Sean M y M′ dos AFDs, decimos que son equivalentes si L(M)=L(M`). Según lo que hemos dicho hasta el momento los AFDs se caracterizan por las palabras que aceptan y es menos importante la estructura interna de la máquina, el número de estados, cuántos estados finales tenga, etc… Digamos que un AFD es principalmente una especie de filtro de todas las cadenas posibles sobre el alfabeto de entrada. Los AFDs tienen muchas utilidades, en particular a nosotros nos interesa especialmente su utilidad como analizadores léxicos. Cuando, por ejemplo, en un programa necesitamos una expresión algebraica del tipo (a+b)*c/(d+e) debe estar correctamente escrita y de comprobarlo se encarga precisamente un analizador construido a partir de un autómata. Lo más normal es que tengamos un lenguaje de interés L sobre un alfabeto Σ y construyamos un AFD cuyo lenguaje sea precisamente L.

10.2. Ejemplo: Construir un AFD sobre el alfabeto Σ={0,1} cuyo lenguaje sea L={cadenas que terminan en 00}