estudiante

Facultad de Ciencias de la Administración
Escuela de Ingeniería de Sistemas y Telemática
Teoría de la Computación II






Tema

Autómatas Finitos Deterministicos





Autor:07/10/2012


Índice

Contenido














Introducción

Un Autómata Finito Determinístico es un dispositivo donde el siguiente estado de la transición esta dadoparticularmente por el estado actual y el carácter de entrada actual.

El AFD se encuentra en un estado inicial y lee una entrada de cadena de caracteres de izquierda a derecha. La función detransición define los estados de transición y es denotada por , donde y ,son estados de , y  es un carácter del alfabeto de entrada. La función de transición indica que cuando un autómata esta en unestado  y recibe el siguiente carácter de entrada, el autómata deberá cambiar al estado . El carácter de entrada no causara transición en caso de ser un carácter vacio.
            El siguiente ejemplomuestra un autómata que acepta cadenas consistentes de únicamente un número par de 0 y 1.

            Donde está definido como:
M(S,0) = B
M(S,1) = A
M(A,0) = C
M(A,1) = S
M(B,0) = S
M(B,1) = CM(C,0) = A
M(C,1) = B
            El diagrama de transición para este autómata es:

            El transición de funciones para un autómata es algunas veces más mostrado de manera másconveniente con una tabla de transición.
 
Entrada
Estado
0
1
S
B
A
A
C
S
B
S
C
C
A
B
            En el ejemplo una cadena aceptada por el DFA es 110101 y una cadena no aceptada es 11101.Objetivo general

Entender el funcionamiento de los algoritmos y su aplicación en base a las clases y objetos.Objetivos específicos

Consolidar conocimientos aprendidos en el aula acerca de los autómatas finitos determinísticos
Elaborar un programa que pueda resolverlos y nos de un mensaje de que si...