Trabajo Colaborativo 2 AUTOMATAS Y LENGUAJES FORMALES

EJERCICIOS A DESARROLLAR

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

ACTIVIDADES ANTES DE MINIMIZAR.

1. Enuncie el autómata en notación matemática

Dado el anterior autómata finito. M = (K, ∑, qo, σ, F).

2. Identifique los componentes del autómata (que tipo de tupla es)

Autómata finito determinista por lo cual su tupla es:

5 tupla A = (Q, Σ, f, q0, F) donde:

Q es un conjunto de estados.

Σ es el alfabeto de entrada

f: Q X Σ → Q es la función (total) de transición.

q0 ∈ Q es el estado inicial.

F ⊆ Q es el conjunto de estados finales

Q/E0={ C1(para estados finales) , C2(para los demás estados)}

Q/E0={ C1(q0) , C2(,q1,q2,q3,q4,q5,q6)}

Q/E1={ C1(q0) , C2(,q1,q2,q3,q4,q5)}

y la función (que también se puede describir así) está dada por:

 = {(q0,0,q1),(q0,1,q2),(q1,0,q0),(q1,1,q3),(q2,0,q3),(q2,1,q0),(q3,0,q5), (q3,q4),(q4,0,q0),(q4,1,q6),(q5,0,q6),(q5,0,q0),(q6,0,q5),(q6,,q4)}

3. Identifique la tabla de transición correspondiente

Q/E1 0 1

q0 q1 q2

q1 q0 q3

q2 q3 q0

q3 q5 q4

q4 q0 q6

q5 q6 q0

q6 q5 q4

0 1

C2 C2

C1 C2

C2 C1

C2 C2

C1 C2

C2 C1

C2 C2

4. Identifique el lenguaje que reconoce y enuncie cinco posibles cadenas válidas que terminen en el estado “halt” .

El lenguaje que reconoce será el de todas las posibles cadenas ω que empiecen por 0 ó por 1 y que terminen en 0 ó 1, bajo ciertas condiciones (propiedad) que resulta compleja, (ER) por eso es que se minimiza o reduce el autómata.

5. Encuentre la expresión regular válida.

((11+1010+1001+(1011+1000)(11+00)*(10+01))*0(0+110+101+(111+100)(11+00)*(10+01)))*(11+1010+1001+(1011+1000)(11+00)*(10+01))*0

El propósito de las ER (que no son más que simples fórmulas) es representar cada una de ellas un lenguaje.

Comprobación en el simulador.

6. Encuentre su gramática que sea válida para la función de transición (describa sus componentes y como se escriben matemáticamente). Justifíquela si la convierte a la Izquierda o a la derecha. Plásmela en el simulador y recréela. (Debe quedar documentado en el texto el paso a paso que realizan en el simulador)

Definimos o caracterizamos una gramática regular como: Un cuádruplo (V, Σ, R, S) en donde:

V = Es el alfabeto de variables

Σ = Es el alfabeto de constantes

R = Es el conjunto de reglas, es un subconjunto finito de V x (ΣV U Σ )

S= Es el símbolo inicial y es un elemento de V

Estas gramáticas regulares son de la forma:

Lineales por la derecha.- Cuando todas las producciones tienen la forma

A → aB o bien A → a

7. Realice el árbol de Derivación de esa gramática.

8. Identifique si ese árbol o gramática es ambigua o no y plasme las razones de su afirmación.

La gramática no es ambigua porque hay un solo árbol de derivación.

9. Si el árbol de transición es demasiado grande, a su criterio seleccione una regla en la que se detenga por cualquier rama (izquierda o derecha) y plásmelo hasta ahí. (es decir seleccione una cadena válida para este ítem).

.

10.-Explicar el proceso de Minimización (que estados se suprimen y porque).

Se crean dos subconjuntos, uno formado por los estados no finales y otro por los estados finales

No finales Finales

[q1,q3,q4,q5] [q0,q2]

GRUPO q_1,q_3,q_4,q_5 COMO:

Desde q_1 con a se pasa al grupo q_1,q_3,q_4,q_5

Desde q_3 con a se pasa al grupo q_1,q_3,q_4,q_5

Desde q_4 con a se pasa al grupo q_1,q_3,q_4,q_5

Desde q_5 con a se pasa al grupo q_1,q_3,q_4,q_5

Para analizar si q_1,q_3,q_4,q_5 pueden quedaren el mismo grupo se debe analizar qué ocurre con el símbolo b.

Desde q_1 con a se pasa al grupo q_0,q_2

Desde q_3 con a se pasa al grupo q_0,q_2

Desde q_4 con a se pasa al grupo q_1,q_3,q_4,q_5

Desde q_5 con a se pasa al grupo q_1,q_3,q_4,q_5

...