AUTOMATAS Y LENGUAJES FORMALES - TC2

MOMENTO 2 – PLANEACIÓN (DISEÑO DE AF Y AP) ORGANIZACIÓN CON EL GRUPO DE TRABAJO












Elaborado por:
CÉSAR FERNANDO ESPITIA PÉREZ






Grupo: 14





Presentado a:
Carlos Alberto Amaya Tarazona











UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA - ECBTI
AUTÓMATAS Y LENGUAJES FORMALES -301405
SEPTIEMBRE DE 2014
BOGOTA D.C.
PARTE 1: Calcular el autómata mínimo correspondiente al siguiente autómata finito.
1. Enuncie el autómata en notación matemática e identifique que tipo de autómata es.
Notación matemática:
M = (K, Σ, ᵹ, s, F)
M = ({q0,q1,q2,q3,q4,q5,q6,q7}, {0,1}, {ᵹ}, {q0}, {q3,q5})

ᵹ (q0, 0) = q2 ᵹ (q1, 0) = q4 ᵹ (q2, 0) = q3 ᵹ (q3, 0) = q2
ᵹ (q0,1) = q1 ᵹ (q1, 1) = q5 ᵹ (q2, 1) = q4 ᵹ (q3, 1) = q7
ᵹ (q4, 0) = q7 ᵹ (q5, 0) = q6 ᵹ (q6, 0) = q3 ᵹ (q7, 0) = q4
ᵹ (q4, 1) = q6 ᵹ (q5, 1) = q1 ᵹ (q6, 1) = q4 ᵹ (q7, 1) = q5
Este es un autómata de tipo AFD (Autómata Finito Determinista) debido a que desde un estado determinado las posibles funciones de transición para cada símbolo del lenguaje, no son ambiguas y solopermiten dirigirse hacia un único estado siguiente.

2. Identifique los componentes del autómata (que tipo de tupla es)
Este autómata AFD esta conformado por la siguiente quíntupla de elementos:
Los estados existentes.
K = {q0,q1,q2,q3,q4,q5,q6,q7}
El lenguaje o símbolos aceptados por el autómata.
Σ = {0,1}
La función de transición entre los estados existentes de acuerdo al símbolo determinado.ᵹ = {q0,q1,q2,q3,q4,q5,q6,q7} x {0,1} → {q0,q1,q2,q3,q4,q5,q6,q7} → q0 → {q3,q5}
El estado inicial del autómata.
s = q0
El estado o estados finales del autómata.
F = {q3,q5}

3. Identifique la tabla de transición correspondiente
ᵹ
0
1
→ q0
q2
q1
q1
q4
q5
q2
q3
q4
# q3
q2
q7
q4
q7
q6
# q5
q6
q1
q6
q3
q4
q7
q4
q5
4. Identifique el lenguaje que reconoce (no en notaciónde ER) y enuncie cinco posibles cadenas válidas que terminen en el estado “halt” y cinco cadenas no válidas.
Lenguaje que reconoce el autómata es el conjunto de cadenas “w” que inicien por el símbolo “0” o “1” y que terminen en “0” o “1” respetando unas condiciones que son complejas y por tanto es necesario minimizar el autómata para poder presentarlo en ER.
Cadenas validas:010101010101111111
01011111000000
010100000000
1111111111111111
0000000000000000
Cadenas no validas:
1010111010001
110100100001111
111111100101000
0100111111
1000000000000000
5. Encuentre la expresión regular válida. (se genera de forma manual, asociando cada operador y sentencia al diagrama de moore de forma explicativa). No se genera con el JFLAP.
La expresión regular del autómata se construyehaciendo recorridos cíclicos de expresiones validas elementales como por ejemplo las halladas en el punto anterior:
Expresión valida 00, al recorrer el autómata infinitas veces pero al menos una vez con esta expresión será valida por terminar en el estado q3 y se moverá así:
00 = (q0, q2, q3) → (00)* = (q3, q2, q3)* luego la expresión es: 00(00)*

del mismo modo ocurre con la expresión 11 terminandoen q5 así:
11 = (q0, q1, q5) → (11)* = (q5, q1, q5)* luego la expresión es: 11(11)*

ocurre también con la expresión 1010 siempre que ocurra al menos una vez:
1010 = (q0, q1, q4, q6, q3) → (1010)* = (q3, q7, q4, q6, q3)*
luego la expresión es: 1010(1010)*

así con la expresión 0101 siempre que ocurra al menos una vez:
0101 = (q0, q2, q4, q7, q5) → (0101)* = (q5, q6, q4, q7, q5)*
luegola expresión es: 0101(0101)*

la expresión 1001 siempre que ocurra al menos una vez:
1001 = (q0, q1, q4, q7, q5) → (1001)* = (q5, q1, q4, q7, q5)*
luego la expresión es: 1001(1001)*

la expresión 0110 siempre que ocurra al menos una vez:
0110 = (q0, q2, q4, q6, q3) → (0110)* = (q3, q2, q4, q6, q3)*
luego la expresión es: 0110(0110)*

de este modo se puede construir una expresion...