Automatas

Escuela de Ciencias Básicas Tecnología e Ingeniería ECBTI

Programa Ingeniería de Sistemas

AUTOMATAS Y LENGUAS FORMALES

MOMENTO 1

Curso 301405_35

Estudiante:

RICHARD ANDRES DAJOME ARIZALA

Código # 87432703

Tutora

ANGELA MARIA GONZALEZ

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD

CEAD PASTO

Marzo de 2015

HE DESARROLLADO LOS EJERCICIOS 1, 2, 3

PUNTO N° 1.

Dado el siguiente Autómata M Finito:

Dónde:

Es el estado inicial

Donde la función de transición está dada por:

× → → →

TABLA DE TRANSICIÓN.

Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el concepto de determinismo)

-> Ø Ø

Ø Ø Ø

Ø Ø Ø

# Ø Ø

# Ø Ø Ø

El autómata corresponde a un autómata finito no determinista con transiciones (AFND ) al que se le permite cambiar de estado sin necesidad de consumir o leer un símbolo de entrada porque cumple con uno de los requisitos para no ser determinista cuando al analizar el autómata en el estado inicial en un cierto instante y si el símbolo actual es , en el instante siguiente, el autómata puede decidir de forma no determinista entre “leer el símbolo y cambiar al estado y continuar su recorrido”, o bien, “cambiar al estado sin mover el cabezal de lectura y llegar al estado final ”.

PUNTO N° 2

Elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto).

Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales.

Es un autómata de estados finitos M identificado como un quíntuplo por los siguientes elementos

Dónde es el conjunto de identificadores (símbolos) de estados; es decir cada estado se identifica con un nombre ,

El elemento es el alfabeto de entrada que contiene los símbolos , un estado inicial que pertenece al conjunto de estados en otras palabras , dos estados final

Este pertenece y está inmerso dentro del conjunto de estados en otras palabras , y finalmente una función de

...