• Categories
• Función (Matemáticas)
• Física y matemáticas
• Matemática
• Ciencia
• Informática y tecnología de la información

Citation preview

AUTOMATAS Y LENGUAJES FORMALES

Fase 3 Modelar problemas de Lenguajes Independientes del Contexto.

Presentado por: DERLY CORONADO

Presentado a: JHEIMER JULIAN SEPULVEDA

UNIVERSIDAD NACIONAL ABIERTA Y ADISTANCIA UNAD ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERÍA ECBTI SAN JOSE DEL FRAGUA 2019

EJERCICIOS DE LA FASE 2 ACTIVIDAD INDIVIDUAL 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 de la Cédula o TI 1y9 2y8 3y7 4y6 5y0

Ejercicio Ejercicio Ejercicio Ejercicio Ejercicio Ejercicio

1 2 3 4 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

Registre aquí el Ejercicio a trabajar. Por favor agregue la imagen

Caracterización En este espacio se realiza: del autómata a - Mediante la definición formal pila características del autómata

explicar

las

Un autómata a pila es una séptupla: AP= (Σ, Γ, Q, A0, q0, f, F) Donde: 1. Σ es el alfabeto de entrada 2. Γ es el alfabeto de la pila 3. Q es un conjunto finito de estados 4. A0 ∈ Γ es el símbolo inicial de la pila 5. q0 ∈ Q el estado inicial del autómata 6. F ⊆ Q es el subconjunto de estados finales 7. f es una aplicación denominada función de transición de ternas (estado, símbolo de entrada o λ, símbolo de pila) en el conjunto de las partes Q×Γ* En este caso: 𝛴 = {𝑎, 𝑏, } 𝛤 = {𝐴, 𝐵, 𝑍} 𝑄 = {𝑞0, 𝑞1, } 𝐴0 = {𝐴, 𝐵, 𝜆} 𝑞0 = {𝑞0} 𝐹 = {𝑞1}

A partir de esta configuración realiza transiciones según la definición de la función f. 𝑓 ∶ 𝑒𝑠 𝑢𝑛𝑎 𝑓𝑢𝑛𝑐𝑖ó𝑛 𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑖𝑐𝑖ó𝑛 𝒇 𝒇 𝒇 𝒇 𝒇

-

(𝒒𝟎, 𝒂, 𝒁) = {(𝒒𝟎, 𝑨)} (𝑞0, 𝑎, 𝐴) = {(𝑞0, 𝐴𝐴)} (𝑞0, 𝑏, 𝐴) = {(𝑞1, 𝐵)} (𝑞1, 𝑏, 𝐴) = {(𝑞1, 𝐵)} (𝑞1, 𝑏, 𝐵) = {(𝑞1, 𝜆 )}

Realizar un cuadro comparativo de la Equivalencia entre AP por vaciado de pila y AP por estado final. Cuadro comparativo de la Equivalencia entre AP por vaciado de pila y AP por estado final. AP por vaciado de pila Lenguaje de autómata a pila por vaciado a pila. 𝑳𝑽(𝑨𝑷) = { 𝒙 | (𝒒𝟎, 𝒙, 𝑨𝟎) ├ ∗ (𝒑, 𝝀, 𝝀) 𝒄𝒐𝒏 𝒑 ∈ 𝑸}

AP por estado final Lenguaje de autómata a pila por estado final. 𝑳𝑭(𝑨𝑷) = {𝒙 |(𝒒𝟎, 𝒙, 𝑨𝟎)∗ (𝒑, 𝝀, 𝑿), 𝒄𝒐𝒏 𝒑 ∈ 𝑭, 𝑿 ∈ 𝜞 ∗}

EQUIVALENCIA DE AP Dos autómatas a pilas por vaciado de pila o por estado final son equivalentes, si 𝑨𝑷𝟏 y 𝑨𝑷𝟐 aceptan el mismo leguaje, es decir, si 𝑳(𝑨𝑷𝟏 ) = 𝑳(𝑨𝑷𝟐 ) -

Procedimiento de paso a paso del recorrido de una cadena

Realice de manera detallada y grafica el procedimiento paso a paso del recorrido de una cadena (La cadena la selecciona el estudiante, debe contener como mínimo 8 caracteres) en el autómata a pila. Describir cómo funciona el almacenamiento en la pila, como funciona LIFO, etc. La cadena a ejecutar es: aaaabbbb - Paso 1. El autómata inicia en q0, lee el símbolo de entrada a, y agrega el contenido de la pila. Estado q0

por leer aaaabbbb

Pila Z

- Paso 2… el autómata en el mismo estado q0, lee la segunda letra a y se agrega la pila Estado q0 q0

leer aaaabbbb aaabbbb

Pila Z A

- Paso 3… el autómata en el mismo estado q0, lee la tercera letra a y se agrega la pila. Estado q0 q0 q0

leer aaaabbbb aaabbbb aabbbb

Pila Z A AA

Paso 4… el autómata en el mismo estado q0, lee la cuarta letra a y se agrega la pila. Estado q0 q0 q0 q0

Ejemplo:

leer aaaabbbb aaabbbb aabbbb abbbb

Pila Z A AA AAAA

Gráfico

Realizar la representación utilizando flechas, conexiones, diagramas que permitan ver el funcionamiento del autómata a pila

Para una transición:

F (q, a, A) = {(q1, Z1), (q2, Z2),... (qn, Zn)} - Paso 1: cuando el autómata se encuentra en el estado q, lee el símbolo de entrada a y tiene el símbolo A en la cima de la pila. - Paso 2: El autómata pasará a algún estado q1, eliminará el símbolo A de la pila e introducirá en ella la palabra Zi, quedando la cabeza de Zi en la cima de la pila. - Paso 3: El procedimiento se repite n veces Practicar y verificar lo aprendido

Apoyándose en el simulador JFlap o VAS ejecutar y validar por lo menos cinco cadenas válidas y 5 cadenas rechadas por el autómata. En este espacio adjunta la imagen.