TRABAJO COLABORATIVO CARLOS GIOVANNI HURTADO G Cod: 79764233 UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD

TRABAJO COLABORATIVO

CARLOS GIOVANNI HURTADO G

Cod: 79764233

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD

2017

Ejercicio 2:

Diseñe un AP que lea el siguiente lenguaje L ={(ab*) | (c*d*)} ; es decir todas las combinaciones posibles de cadenas conformadas por los símbolos (a) (b*) o (c*)(d*) (con pila vacía).

[pic 1]

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

Se define con la séptupla: [pic 2]

 Alfabeto de entrad = {a, b, c, d}[pic 3]

=  Alfabeto de la pila = {}[pic 4][pic 5]

 Conjunto finito de estados = {q0, q1, q2, q3}[pic 6]

= Símbolo inicial de la pila,   = {}[pic 7][pic 8][pic 9][pic 10]

 Estado inicial,   = {q0}[pic 11][pic 12][pic 13]

 Funcion de transición (terna: estado, símbolo de entrada o λ, símbolo de pila =[pic 14][pic 15]

[pic 16]

[pic 17]

[pic 18]

[pic 19]

[pic 20]

 Estados finales  F    = {q1, q3}[pic 21][pic 22][pic 23][pic 24]

1. Determine el lenguaje que reconoce el AP.

L = {(ab*) | (c*d*)}

1. Justifique y asocio o evidencie si el diseño es un APND o un APD:

Decimos que un autómata a pila es determinista si se verifica lo siguiente:

1. [pic 25]

[pic 26]

1. :[pic 27]

[pic 28]

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

[pic 29]

Aquí se puede observar el estado inicial “q0”, carácter de la pila “z” y la cadena que falta por leer.

[pic 30]

Aquí se observa que se pasó al estado “q2” con transición vacía y sin afectar la pila.

[pic 31]

Aquí se observa cómo cambia al estado “q3” sin requerir carácter ni condición de pila.

[pic 32]

En el estado “q3” inicia a consumir los caracteres sin cambio de estado.

[pic 33]

Finalmente con cuando lee el carácter “d” pasa a estado de aceptación  y la memoria de la pila no fue afectada.

1. Plasme las imágenes del recorrido de ese Traceback para cada movimiento en el documento.

[pic 34]

...