Actividad Momento 1 Automatas Y Lenguaje Formales

Actividad Momento 1

Dada la siguiente tabla de transición:

ᵟ a b

q0

q1, q4, q3 q2

q1 q5, q4 q2

# q2 ф ф

q3 q4, q5 q4, q5, q2

q4 ф ф

q5 ф ф

Exprese el autómata en notación matemática. Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta.

Solución.

La expresión matemática para este autómata es:

M=(Σ,K,δ,S,F).

M=({q0,q1,q2,q3,q4,q5},{a,b},δ,q0,{q2})

El autómata es un AFD (Autómata Finito Determinista), porque posee la característica del determinismo la cual permite saber a partir del estado actual y del símbolo actual de entrada poder determinar en forma exacta cual será el estado siguiente.

Identifique los elementos (tupla que es) (asociada 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.

Solución.

Formalmente, un autómata finito determinista o no determinista se define como una 5-tupla (Q, Σ, δ, S, F).

Es un conjunto de estados.

Es un alfabeto.

S € Q Es el estado inicial;

Es una función de transición.

Es un conjunto de estados finales o de aceptación.

K= { q0,q1,q2,q3,q4,q5}

Σ= {a,b}

S= q0

F= {q2}

Autómata: La palabra autómata evoca algo que pretende imitar las funciones propias de los seres vivos, especialmente relacionadas con el movimiento, por ejemplo el típico robot antropomorfo. Un ejemplo de una “maquina real” que automatiza un proceso puede ser una máquina empacadora de algún producto que se fabrique enserie y con una serie de instrucciones, pasos y características definidas e iguales para cada salida (producto final).

Alfabeto: Un Alfabeto es un conjunto finito A. Sus elementos se llamaran símbolos o letras. Para denotar el alfabeto se usara el símbolo Σ o en algunos casos se especificaran con las primeras letras mayúsculas del abecedario, dependiendo como se formule el problema. Los símbolos de un alfabeto pueden ser números, letras, entre otros y suelen estar escritos en minúsculas. Ejemplo: Sea A = {0,1} indica el Alfabeto A compuesto por los símbolos 0,1

Estado: Un estado es un conjunto particular de instrucciones las cuales serán ejecutadas en respuesta a la entrada de la máquina. Se puede pensar en el estado como algo análogo a la memoria principal de la computadora. El comportamiento del sistema es una función de (a) la definición del autómata, (b) la entrada y (c) el estado actual.

Una función de transición en teoría de autómatas, es una función que define las transiciones entre los estados de una Máquina de Turing, de un autómata finito o de otro tipo de autómatas. Se describe mediante una tabla de transición de estados

Identifique el lenguaje que genera. (no se trata de explicarlo o formularlo en notación de una ER)

Solución.

El lenguaje que genera es el siguiente:

...