AUTOMATAS Y LENGUAJES FORMALES
UNIDAD 2 - LENGUAJES INDEPENDIENTES DEL CONTEXTO Y SUS MÁQUINAS
PRESENTADOR POR:
YAIR ALEJANDRO SOSA
CÓDIGO 80002937
GRUPO: 301405_10
PRESENTADO A:
ROLANDO FABIAN JUNCO
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA
OCTUBRE DE 2019
EJERCICIOS DE LA FASE 2
ACTIVIDAD INDIVIDUAL
Cada estudiante resuelve el taller propuesto en el objeto virtual de aprendizaje
lenguajes de libre contexto propuesto en el entorno de conocimiento Unidad 2.
De acuerdo al último dígito de su cédula o tarjeta de identidad, identifique el ejercicio
asignado en la siguiente tabla:
Último dígito Ejercicio
de la Cédula o
TI
1y9 Ejercicio 1
2y8 Ejercicio 2
3y7 Ejercicio 3
4y6 Ejercicio 4
5y0 Ejercicio 5
ACTIVIDAD 1: Autómatas de Pila
1. Ejercicio 1 2. Ejercicio 2
3. Ejercicio 3 4. Ejercicio 4
5. Ejercicio 5
El diseño solicitado corresponde al diligenciamiento de la siguiente tabla:
EJERCICIO A
TRABAJAR
Caracterización En este espacio se realiza:
del autómata a - Mediante la definición formal explicar las características del
pila autómata
AP= (∑, r Q, A0, q0, f, F) (Autómata de Pila)
∑ = {a, b} (Alfabeto)
r = {A, AA, B, Z} (Alfabeto de pila)
Q = {q0, q1} (Estados)
A0 = Z (Símbolo inicial de la pila)
q0 = q0 (Estado inicial)
F = {q1} (Estado final)
f = Función de transición
ơ = (q0, a, Z), (q0, A)
ơ = (q0, a, A), (q0, AA)
ơ = (q0, b, A), (q1, B)
ơ = (q1, b, A), (q1, B)
ơ = (q1, b, B), (q1, ʎ)
- Realizar un cuadro comparativo de la Equivalencia entre AP
por vaciado de pila y AP por estado final
Dos autómatas a pila AP1 y AP2, son equivalentes, si aceptan
el mismo lenguaje, es decir, si L(AP1) =L(AP2).
El conjunto de lenguajes aceptados por estado final por los
autómatas a pila LAPF es igual que el conjunto de lenguajes
aceptados por vaciado por pila de los autómatas a pila LAPV.
Procedimiento Realice de manera detallada y grafica el procedimiento paso a
de paso a paso paso del recorrido de una cadena (La cadena la selecciona el
del recorrido estudiante, debe contener como mínimo 8 caracteres) en el
de una cadena autómata a pila. Describir cómo funciona el almacenamiento
en la pila, como funciona LIFO, etc.
Cadena de caracteres (aaaabbbb)
- Paso 1: cuando el autómata se encuentra en el estado p,
tiene el símbolo Z en la cima de la pila. Cima pila (Z)
Cadena de caracteres (aaaabbbb)
- Paso 2: cuando el autómata se encuentra en el estado q, lee
la cadena a y elimina el símbolo Z que tiene en la cima de la
pila e introduce el símbolo A. Cima pila (A)
Cadena de caracteres (aaaabbbb)
- Paso 3: cuando el autómata se encuentra en el estado p, lee
nuevamente la cadena a elimina el símbolo A que tiene en la
cima de la pila e introduce el símbolo AA. Cima pila (AA)
Cadena de caracteres (aaaabbbb)
- Paso 4: cuando el autómata se encuentra en el estado q, lee
de nuevo la cadena a elimina el símbolo Z que tiene en la
cima de la pila e introduce el símbolo A. Cima pila (AAA)
Cadena de caracteres (aaaabbbb)
- Paso 5: cuando el autómata se encuentra en el estado p, lee
nuevamente la cadena a elimina el símbolo A que tiene en la
cima de la pila e introduce el símbolo AA. Cima pila (AAAA)
Cadena de caracteres (aaaabbbb)
- Paso 6: cuando el autómata se encuentra en el estado q q0,
lee la cadena b elimina el símbolo A que tiene en la cima de la
pila e introduce el símbolo B. Cima pila (BAAA)
Cadena de caracteres (aaaabbbb)
- Paso 7: cuando el autómata se encuentra en el estado p, lee
nuevamente la cadena b elimina el símbolo B que tiene en la
cima de la pila y no toca la pila ya que esta (ʎ). Cima pila
(AAA)
Cadena de caracteres (aaaabbbb)
- Paso 8: cuando el autómata se encuentra en el estado q, lee
nuevamente la cadena b elimina el símbolo A que tiene en la
cima de la pila e introduce el símbolo B. Cima pila (BAA)
Cadena de caracteres (aaaabbbb)
- Paso 8: cuando el autómata se encuentra en el estado q, lee
nuevamente la cadena b elimina el símbolo B que tiene en la
cima de la pila y no toca la pila ya que esta (ʎ). Cima pila
(AA)
Gráfico
Realizar la representación utilizando flechas,
conexiones, diagramas que permitan ver el
funcionamiento del autómata a pila
Para una transición: Cadena de caracteres (aaaabbbb)
ơ = (q0, b, A), (q1, B)
- Paso 1: cuando el autómata se encuentra en el estado q0,
lee la cadena b pasa a estado q1 y elimina el símbolo A que
tiene en la cima de la pila e introduce la palabra B. quedando
la cabeza de B en la cima de la pila.
Practicar y Apoyándose en el simulador JFlap o VAS ejecutar y validar
verificar lo por lo menos cinco cadenas válidas y 5 cadenas rechadas por
aprendido el autómata. En este espacio adjunta la imagen.
