trabajo colaborativo 2

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

Programa Ingeniería de sistemas Autómatas Y Lenguajes Formales

301405A

Página 1

Trabajo Colaborativo # 2

Aporte Individual 1

Presentado Por:

Andrés Julián Mendoza Enríquez Código: 13749054

Grupo # 09

Presentado a:

Ing. Carlos Alberto Amaya Tarazona

UNIVERSIDAD ABIERTA Y A DISTANCIA (UNAD)

SANTANDER/BUCARAMANGA

30 DE ABRIL DE 2014



301405A

Página 2

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

Autómata finito dado por:

M = (K, ∑, δ, q0, F)

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

Dónde:

K = {q0, q1, q2, q3, q4, q5, q6} (Conjunto de estados)

∑ = {1,0} (Alfabeto de entrada)

q0 es el estado inicial y

F = {q6} (F C K, conjunto de estados finales).



301405A

Página 3

Donde la función de transición:

δ = {q0, q1, q2, q3, q4, q5, q6} x {1, 0} → {q0, q1, q2, q3, q4, q5, q6} → q0 → {q0}

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, 1) = q4

δ(q4, 0) = q0 δ(q4, 1) = q6

δ(q5, 0) = q6 δ(q5, 1) = q0

δ(q6, 0) = q5 δ(q6, 1) = q4

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

Es un Autómata Finito Determinístico, debido a que para un estado y símbolo del alfabeto dado,

existe un y solo un estado siguiente.

5-tupla: A= (Q, ∑, δ, q0, F)

Q son todos los estados.

∑ es un alfabeto.

δ: Q X ∑ → Q es una función de transición de un AFD

q0 ϵ Q es el estado inicial

F C Q es un conjunto de estados finales

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

δ(q0, 0) = q1 δ(q0, 1) = q2

δ(q1, 0) = q0 δ(q1, 1) = q3

δ(q2, 0) = q3 δ(q2, 1) = q0

δ(q3, 0) = q5 δ(q3, 1) = q4

δ(q4, 0) = q0 δ(q4, 1) = q6

δ(q5, 0) = q6 δ(q5, 1) = q0



301405A

Página 4

δ(q6, 0) = q5 δ(q6, 1) = q4

3. Identifique la tabla de transición correspondiente.

δ 0 1

→#q0 q1 q2

q1 q0 q3

q2 q3 q0

q3 q5 q4

q4 q0 q6

q5 q6 q0

q6 q5 q4

q0 es el estado inicial y final del AFD.

La tabla de transición correspondiente a este autómata, generado en el simulador Visual

Autómata Simulator VAS.



301405A

Página 5

4. Identifique el lenguaje que reconoce y enuncie cinco posibles cadenas válidas que

terminen en el estado “halt”

L = {ω є {1, 0}* | ω = 1i 0i, i >=1}

Las siguientes son 5 cadenas validas posibles:

1010

101101

1001

110101

01100110

5. Encuentre la expresión regular válida. El propósito de las ER (que no son más

que simples fórmulas) es representar cada una de ellas un lenguaje).



301405A

Página 6

Comprobación de las posibles cadenas validas en JFLAP:

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) Las gramáticas

son mecanismos generadores de lenguajes, es decir, nos dicen cómo podemos

obtener o construir palabras de un determinado lenguaje.

Se ejecuta el simulador y se da clic en Finite Automaton



301405A

Página 7

Se genera el autómata propuesto



301405A

Página 8

Se da clic en Convert, luego en Convert to Grammar.



301405A

Página 9

La gramática valida por tanto es.

IZQUIERDA DERECHA

S → λ

S → 1B

S → 0A

F → 1D

D → 1F

C → 1D

A → 1C

B → 0C

E → 1S

B → 1S

D → 0S

A → 0S

F → 0E

E → 0F

C → 0E

La conversión es a la izquierda porque es lineal a la derecha y es generado por el simulador a

la derecha.

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

El árbol de derivación es muy grande para mostrarlo gráficamente.

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

afirmación.



301405A

Página 10

Es una gramática libre de contexto la cual solo está asociada con un árbol de derivación para

cualquier cadena de lenguaje, por tanto se puede afirmar que no es una gramática ambigua.

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).

Se obtiene el árbol de transición por la derecha para la cadena valida 1010:

(S→1B)(B→0C)(C→1D)(D→0S)

REGLA DERIVACION

S→1B 1B

B→0C 10C

C→1D 101D

D→0S 1010S

S→λ 1010



301405A

Página 11

Actividades Para El Ejercicio A Minimizar O Ya Minimizado:

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

Se crean los conjuntos formados por los conjuntos finales y los no finales.

FINALES NO FINALES

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

Se le aplica a los subconjuntos la transformación AFD, para los subconjuntos la transición 0.

FINALES NO FINALES

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

0 q1 q0, q0, q3, q5, q5, q6



301405A

Página 12

Se separan los estados del subconjunto que al aplicarle la transición se comportan de manera

diferente a los demás de este, el que se desplaza hacia el estado no final es

FINALES NO FINALES

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

Se realiza el mismo procedimiento para los subconjuntos de transición 1.

FINALES NO FINALES

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

1 q2 q0, q0, q3, q4, q4, q6

Se juntan las dos transiciones.

FINALES NO FINALES

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

1 q2 q0, q3, q4, q4, q6 q0

0 q1 q0, q3, q5, q5, q6 q0

Se procede a realizar la tabla de transición del autómata minimizado, para los subconjuntos

que tienen más de un estado se elige un representante del subconjunto y se reemplaza en la

tabla de transición para de esa forma minimizar el autómata.

AUTOMATA

MINIMIZADO ELIMINACION DE

ESTADOS NUEVO

AUTOMATA

ESTADOS FINALES

1 0 q0 q2 q1

1 0 q0 q2 q1

1 0 q0 q2 q1

ESTADOS NO FINALES

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

q1 q0 q0

q3, q0, q2



301405A

Página 13

11. Que transiciones se reemplazan o resultan equivalentes.

1 0

q2 q0 q3

q3 q4 q5

q4 q6 q0

q5 q0 q6

q6 q4 q5

12. Escribir la función de transición del nuevo autómata.

δ= Q x ∑→Q

δ(q0, 0) = q2 δ(q0, 1) = q1

δ(q1, 0) = q3 δ(q1, 1) = q0

δ(q2, 0) = q0 δ(q2, 1) = q3

δ(q3, 0) = q1 δ(q3, 1) = q2

La tabla de transición correspondiente a este autómata, generada en el simulador Visual

Autómata Simulator VAS.

14. Compruebe una cadena válida para esa expresión regular.

Se comprueba la expresión regular con la cadena valida 110101 (Ver imagen del punto 16)



301405A

Página 14

15. Identificar el lenguaje que reconoce y cinco posibles cadenas válidas

El lenguaje que reconoce es L= {A ϵ {1, 0} | A= 1i0i, i>=1}

Las cadenas posibles son:

0101

0110

010100

101101

110011

16. Identificar su gramática. Demuéstrela para una cadena válida del autómata.

Esta es la gramática generada por el autómata.

Demostración para la cadena valida 101101.



301405A

Página 15

17. Compare la gramática con el autómata antes de minimizar (ya sea por la

izquierda o derecha).

Al ser comparada la gramática del autómata minimizado con el autómata original, se puede

observar que resulta ser aprobada tanto por la izquierda como por la derecha y en cualquier

cadena válida para el autómata ya sea minimizado o en su estado normal.



301405A

Página 16

18. El autómata nuevo expresarlo o graficarlo con su respectivo diagrama de Moore.

19. Identificar sus tablas de Transición (plasmarlas)

δ 1 0

q0 q1 q2

q1 q0 q3

q2 q3 q0

→# q3 q2 q1

20. Plasmar los pasos de minimización en el simulador (compárelos con el proceso

manual que está explicando) y capturar los procesos en imágenes para ser

documentadas en el texto.

Se construye el autómata en el simulador JFLAP



301405A

Página 17

Se selecciona en el menú Convert y luego en Minimize DFA.



301405A

Página 18

Se seleccionan los estados no finales y se da clic en Complete Subtree, luego se hace clic en

los estados finales y en Complete Subtree.

Clic en Finish y después en Complete para ver el autómata resultante.



301405A

Página 19

2. Construya el autómata de Pila Correspondiente

Diseñe un APD que acepte: El lenguaje de la cadena vacía, que además acepte cualquier cadena

que contenga un número de “y” menor o igual que el de “x” y puede ser en cualquier orden. El

diseño también debe permitir aceptar las cadenas con la pila vacía.

21. Describa el autómata en notación matemática.

L= {xn+1yn}

Séptupla M= (Q, A, B, Δ, q0, Z0, F)

M= ({q0, q1, q2, q3, q4}, {x,y}, {A}, Δ, q0, x, {q2})

Las posibles cadenas validas son:

xxyx

xyxyx

xxyxyx

22. Grafíquelo en JFLAP y realice el “Traceback” para las transiciones. (Las columnas

para un AP son: El estado en que se encuentra el autómata, lo que falta por leer de la

palabra de entrada, y el contenido de la pila).



301405A

Página 20

Traceback para las transiciones: se da clic en una de las cadenas aceptadas por el programa

y luego en view trace, se realiza el paso correspondiente a cada cadena para así ver su

tracback.



301405A

Página 21

23. Plasme las imágenes y capturas en el documento. (Documente el proceso)

Se realizó en el punto anterior y se explica como se encuentran las traceback para las

transiciones.

24. Muestre el diagrama correspondiente de estados.

Para hallar el diagrama correspondiente de estados se debe realizar el procesamiento completo

de una cadena de entrada que depende del contenido de pila.

ESTADO POR LEER PILA

q Xxyx

q Xxyx x

q Xyx xx

q Yx xxy

q X xxyx



301405A

Página 22

25. Identifique los contenidos (el recorrido para cada interacción) de la pila y el

estado de parada. Realícelo con una cadena válida.

Se realiza para la cadena valida xxyxyx, se muestra el recorrido



301405A

Página 23

3. Gramáticas

Sean L1 el lenguaje generado por la gramática G1

26. Identifique que tipo de gramática es. Justifique su respuesta.

Es una gramática de contexto libre porque se especificaron las reglas para conseguir o generar

las cadenas de un lenguaje válidas para el autómata

27. Identifique los elementos (tupla) que es.

5-tupla: A= (Q, ∑, δ, q0, A)

Q son todos los estados.

∑ es un alfabeto.

δ: Q X ∑ → Q es una función de transición de un AFD

q0 ϵ Q es el estado inicial

ACQ es un conjunto de estados finales

A= ({q0, q1, q2, q3}, {1,0}, δ, q0, {q3})



301405A

Página 24

28. Obtener el autómata Finito para la gramática (plasme los diagramas de Moore)

29. Identifique el Lenguaje que generan. Identifique si es lineal por la derecha o la

izquierda.

El lenguaje que genera es L= {A ϵ {1, 0} I A= 1n+10n, donde n>=1}

La conversión es a la derecha porque es lineal a la izquierda.



301405A

Página 25

30. Plasme la secuencia y árbol de derivación la cadena 0101 (Use el simulador para

verificarla). E identifique que producciones intervienen. Para justificar sus

respuestas puede apoyarse en la simulación que le dé el software JFLAP

Se convierte a una FA el autómata y luego se observa si la cadena 0101 es aceptada.

Intervienen en esta producción (q0, q1, q2, q3) es decir todo el árbol del autómata.

trabajo colaborativo 2

Documents

Transcript of trabajo colaborativo 2