automatas

AUTOMATAS Y LENGUAJES FORMALES

TRABAJO COLABORATIVO 2

1. Calcular el autómata mínimo correspondiente al siguiente autómata finito



1. Autómata en notación matemática
A= (Q, Σ, q0, δ, A)
Q es un conjunto de estados;
Σ es un alfabeto;
δ: Q x Σ → Q es una función de transición para un AFD;
q0 ϵ Q es el estado inicial;
A C Q es un conjunto de estados finales o de aceptación.2. Identificando los componentes del Autómata (que tipo de tupla es)
Conjunto de estados: Q = {q0, q2, q3, q4, q5, q6}
Alfabeto: Σ = {0; 1}
Estado inicial: q0
Conjunto de estados finales: A = {qo}

Función de transición:

δ:=(q0,0) = q1 δ:=(q0,1) = q2
δ:=(q1,0) = q0 δ:=(q1,1) = q3
δ:=(q2,0) = q3 δ:=(q2,1) = q0
δ:=(q3,0) = q4 δ:=(q3,1) = q5
δ:=(q4,0) = q0 δ:=(q4,1) = q0
δ:=(q5,0) =q6 δ:=(q5,1) = q0
δ:=(q6,0) = q5 δ:=(q6,1) = q4

El autómata es de tipo determinista ya que de cualquiera de sus estados sale un solo símbolo para otro estado determinándose con exactitud cuál es su llegada.

3. Tabla de transición


0
1
# q0
q1
q2
q1
q0
q3
q2
q3
q0
q3
q4
q5
q4
q0
q6
q5
q6
q0
q6
q5
q4






4. Lenguaje que reconoce y5 posibles cadenas validas que terminan en el estado Halt
El lenguaje que reconoce son de cadenas que siempre contienen un numero par de ceros y de unos.
Posibles cadenas reconocidas
00
11
00111100
0110
0101
010010
1010
101101
101110




5. Expresión regular

[00 + 11 + (01 + 10)(1(11)*0 + 0(00)*1) ]*


6. Gramática válida para la función de transición
G = (V, , P, S)
G ={{A, B, C, S}, {0, 1}, S, P}

Descripción de los componentes de G
Alfabeto de variables: V = {S, A, B,C D, E}
Alfabeto de constantes:
Símbolo inicial: S


Conjunto de reglas o producciones: P:
S 
S  0A
S  1B
A  0S
A  1C
B  0C
B  1S
C  0E
C  1D
D  0S
D  1F
E  0F
E  1S
F  1D
F  0E







7. Árbol de derivación

Para la cadena válida: 0110Árbol de derivación obtenido en JFlap


8. Identificando si el árbol o gramática es ambigua o no
La gramática no es ambigua ya no es posible generar dos árboles de derivación diferentes para una misma palabra. También podemos decir que no hay ambigüedad porque el autómata del que partimos es determinístico.
Por ejemplo para la cadena 1111 solo es posible generar un único árbol dederivación que es:



10. Proceso de minimización del autómata
Paso 1: Se divide el conjunto de estados en dos subconjuntos, uno formado por los estados no finales y el otro por los estados finales.

No finales
Finales

{q1, q2, q3, q4, q5, q6}
{q0 }

Paso 2: Aplicar a los dos subconjuntos formados en el paso anterior, las transiciones del AFD, empezaremos por la transición “0”

Nofinales
Finales

{q1, q2, q3, q4, q5, q6}
{q0 }
0
q0 q3 q5 q0 q6 q5
q1




Paso 3: Dado que en q1 y en q4 ocurre un salto a q0 que pertenece a otro subconjunto separamos q1 con q4 del resto formándose así un nuevo subconjunto de estados no finales.


No finales
Finales

{q2, q3, q5, q6} {q1, q4}
{q0 }

Paso 4: Repetimos el proceso del paso 2


No finales
Finales{q2, q3, q5, q6} {q1, q4}
{q0 }
0
q3 q5 q6 q5 q0 q0
q1

Paso 5: Al no haber nuevos saltos de un subconjunto a otro repetimos el paso 2 pero esta vez con la siguiente transición (transición 1)

No finales
Finales

{q2, q3, q5, q6} {q1, q4}
{q0 }
0
q3 q5 q6 q5 q0 q0
q1
1
q0 q4 q0 q4 q3 q6
q2

Paso 6: En la transición con 1 los estados q2 yq5 por un lado y los estados q3 y q6 transitan a diferentes subconjuntos de estados por lo que hacemos una nueva separación en los estados no finales

No finales
Finales

{q2, q5} {q3, q6} {q1, q4}
{q0 }
0
q3 q6 q5 q5 q0 q0
q1
1
q0 q0 q4 q4 q3 q6
q2

Paso 7: Como los estados de un mismo subconjunto ya no transitan a estados de diferentes...