TRABAJO COLABORATIVO CARLOS GIOVANNI HURTADO G Cod: 79764233 UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD
Enviado por gio641 • 16 de Abril de 2017 • Trabajo • 327 Palabras (2 Páginas) • 275 Visitas
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]
- 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]
- Determine el lenguaje que reconoce el AP.
L = {(ab*) | (c*d*)}
- 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:
- [pic 25]
[pic 26]
- :[pic 27]
[pic 28]
- 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.
- Plasme las imágenes del recorrido de ese Traceback para cada movimiento en el documento.
[pic 34]
...