Guia de Autómatas Finitos Deterministas (AFD) Parte1

Ads1

Autómatas Finitos Deterministas (AFD). Parte I


Esta es una guía sobre autómatas finitos deterministas que trabajé hace un tiempo con mis estudiantes en la asignatura “Compiladores”, son varios ejemplos que te permitirán comprender los AFD, los ejemplos tienen como finalidad lo siguiente:


  • Evaluar el nivel de comprensión de los AFD.
  • Encontrar los elementos (A,S,F,q0,q1) del autómata partiendo del diagrama.
  • Crear la tabla de transición partiendo del diagrama.
  •  Identificar cuando un AF es o no determinista.

Como lecturas adicionales he publicado en los siguientes enlaces temas relacionados:

PARTE I: En esta primera parte el objetivo es poder comprender cuales son los símbolos de entrada, aceptación y de estado, también a partir del diagrama crear la tabla de transición.

EJEMPLO 1: A partir del siguiente diagrama

Automatas-Finitos-Deterministas-(AFD)-002
Determine:

Los símbolos de entrada              A
Los estados del diagrama             S
Los estados de aceptación           F
El estado inicial                             q1
Ejemplifique gramáticas válidas

SOLUCIÓN:
A = {a, b}
S = {q0, q1, q2}
F = {q0, q1}
q1 = {q0}
Gramáticas validas: aaaa, aba, a, bab, bababab


EJEMPLO 2: A partir del siguiente diagrama determine:

Automatas-Finitos-Deterministas-(AFD)-003

Determine:

Los símbolos de entrada              A
Los estados del diagrama             S
Los estados de aceptación           F
El estado inicial                              q1
Ejemplifique gramáticas válidas

SOLUCIÓN:
A = {a, b, c}
S = {q0, q1, q2}
F = {q0}
q1 = {q0}
Gramáticas validas: abb, aca, cacbaca, bbbaa, baccaaa


EJEMPLO 3: A partir del siguiente diagrama construya la tabla de transiciones y determine los siguientes datos.

Automatas-Finitos-Deterministas-(AFD)-004


Determine:

Los símbolos de entrada              A
Los estados del diagrama             S
Los estados de aceptación           F
El estado inicial                            q1
Ejemplifique gramáticas válidas

SOLUCIÓN:
A = {a, b, c}
S = {0, 1,2,3,4,5}
F = {1,4,5}
q1 = {0}

ESTADOS
ENTRADA DE DATOS
a
b
C
0
1
3
5
1
-
2
-
2
-
1
-
3
-
-
4
4
-
-
-
5
-
-
-


EJEMPLO 4: Construya una tabla de transiciones a partir del siguiente diagrama y escriba símbolos reconocidos por el autómata.

Automatas-Finitos-Deterministas-(AFD)-005


SOLUCIÓN:
ESTADOS
ENTRADA DE DATOS
0
1
1
2
2
2
-
2


EJEMPLO 5: Construya una tabla de transiciones a partir del siguiente diagrama y escriba símbolos reconocidos por el autómata.

Automatas-Finitos-Deterministas-(AFD)-006

SOLUCIÓN:
ESTADOS
ENTRADA DE DATOS
letra
:
Digito
=
1
2
3
5
-
2
2
-
2
-
3
-
-
-
4
4
-
-
-
-
5
-
-
5
-
 


EJEMPLO 6: Construya una tabla de transiciones a partir del siguiente diagrama y escriba un analizador léxico basado en esa tabla.
Automatas-Finitos-Deterministas-(AFD)-007
Gramática valida
Digito, digito, digito
[0-1][0-1][0-1]*    OK

Tabla de transiciones
ESTADOS
ENTRADA DE DATOS
digito
1
3
3
4
4
4


EJEMPLO 7: Dado el siguiente diagrama de transiciones obtener A, S, f, qi, F y decir que lenguaje se genera.
Automatas-Finitos-Deterministas-(AFD)-008
Obtener A, S, f, qi, F

A = {a, b}
S = {q0, q1, q2,q3,q4}
F = {q2,q3,q4}
q1 = {q0}

Tabla de transición


ESTADOS

ENTRADA DE DATOS

a
b
q0
q1, q4
q3
q1
q1
q2
q2
-
-
q3
-
-
q4
-
q4

Lenguaje que genera:

A(a/b)*
a/b*
b

EJEMPLO 8: Dado el siguiente diagrama de transiciones obtener A, S, f, qi, F y decir que lenguaje se genera.
Automatas-Finitos-Deterministas-(AFD)-009
Obtener A, S, f, qi, F
A = {a, b}
S = {q0, q1, q2,q3}
F = {q2}
q1 = {q0}

Tabla de transición


ESTADOS

ENTRADA DE DATOS

a
b
q0
q1
q3
q1
q3
q2
q2
q1
q3
q3
q3
q3

Lenguaje que genera:

A(a/b)


EJEMPLO 9: El siguiente diagrama, ¿Es un diagrama de transición correspondiente a un AFD? ¿Por qué si o porque no?
Automatas-Finitos-Deterministas-(AFD)-010
No es AFD porque existe más de una transición, con el mismo símbolo de entrada (el símbolo a sale de q0 a q1 pero también se retorna a q0), ya que por ello se caracterizan los autómatas finitos no deterministas.



Compartir el contenido del blog contrinuirá para llegar a mas personas interesadas en el tema de los Lenguajes Compiladores, apoyanos y comparte en tus redes sociales.

Namecheap.Com: Cheap Domain Names



Namecheap.com

Incrementa las visitas registrándote en estos directorios

directorio de blogs Blogazos.com. Directorio de Blogs en Español Directorio Web de enlaces mexicanos Directorio de paginas webs 360dir
Derechos Reservados. Postecnologia.com. Con tecnología de Blogger.

Seguidores

Contacto

Nombre

Correo electrónico *

Mensaje *


Compartir

Buscar

Registrate para recibir en tu e-mail todo lo nuevo que se publica en este blog. Contenido exclusivo

Translate / Traducir

Visitas

Comunidad Google+

Seguinos en

Síguenos en Google+ Síguenos en Facebook Seguir en Twitter Sígueme en Youtube Sígueme en Likedin Sígueme en Pinterest Rss feed Sígueme en Slideshare

TxtFull.com y TotalPing.com

Aumenta tus visitas con TxtFull.com y TotalPing.com

Mi Ping en TotalPing.com Protected by Copyscape Plagiarism Software

Mejores PTC del Momento

PopAds.net - The Best Popunder Adnetwork

Entradas Más Leídas

Visitantes Online

Estos usuarios tambien nos han visitado.

Hosting y Alojamiento

Hostgator, NeoThek, Hostinger y GoDaddy Proveedores de Hosting y Dominios

Hosting Gratis Let's Get Back to Business. Start with a $1.99 .COM from GoDaddy.

MBA Ranking

Recuperación de datos

App Developer