• Categories
• Áreas de la informática
• Matemática
• Informática y tecnología de la información

Citation preview

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 explicar las características del pila autómata - Realizar un cuadro comparativo de la Equivalencia entre AP por vaciado de pila y AP por estado final Procedimiento de paso a paso del recorrido de una cadena

- Paso 1… f(q, var, S) = {(q, FNP)} f(q, if, S) = {(q, CTBP), (q, CTBEBP)} f(q, if, B) = {(q, CTB), (q, CTBEB)} f(q, var, B) = {(q, FN)} f(q, cond, C) = {(q, λ)} f(q, ::=, F) = {(q, λ)} f(q, num, N) = {(q, λ)} f(q, ;, P) = {(q, λ)} f(q, then, T) = {(q, λ)} f(q, else, E) = {(q, λ)}

if

cond

then

var

::=

num

;

S

- Paso 2… f(q, var, S) = {(q, FNP)} f(q, if, S) = {(q, CTBP), (q, CTBEBP)} f(q, if, B) = {(q, CTB), (q, CTBEB)} f(q, var, B) = {(q, FN)} f(q, cond, C) = {(q, λ)} f(q, ::=, F) = {(q, λ)} f(q, num, N) = {(q, λ)} f(q, ;, P) = {(q, λ)} f(q, then, T) = {(q, λ)} f(q, else, E) = {(q, λ)}

if

cond

then

var

::=

num

;

C T B P

- Paso 3… f(q, var, S) = {(q, FNP)} f(q, if, S) = {(q, CTBP), (q, CTBEBP)} f(q, if, B) = {(q, CTB), (q, CTBEB)} f(q, var, B) = {(q, FN)} f(q, cond, C) = {(q, λ)} f(q, ::=, F) = {(q, λ)} f(q, num, N) = {(q, λ)} f(q, ;, P) = {(q, λ)} f(q, then, T) = {(q, λ)}

if

cond

then

var

::=

num

;

T B P

f(q, else, E) = {(q, λ)}

-Paso 4… f(q, var, S) = {(q, FNP)} f(q, if, S) = {(q, CTBP), (q, CTBEBP)} f(q, if, B) = {(q, CTB), (q, CTBEB)} f(q, var, B) = {(q, FN)} f(q, cond, C) = {(q, λ)} f(q, ::=, F) = {(q, λ)} f(q, num, N) = {(q, λ)} f(q, ;, P) = {(q, λ)} f(q, then, T) = {(q, λ)} f(q, else, E) = {(q, λ)}

if

cond

then

var

::=

num

;

B P

if

cond then var

::= num ;

Paso 5….. f(q, var, S) = {(q, FNP)} f(q, if, S) = {(q, CTBP), (q, CTBEBP)} f(q, if, B) = {(q, CTB), (q, CTBEB)} f(q, var, B) = {(q, FN)} f(q, cond, C) = {(q, λ)} f(q, ::=, F) = {(q, λ)} f(q, num, N) = {(q, λ)} f(q, ;, P) = {(q, λ)} f(q, then, T) = {(q, λ)} f(q, else, E) = {(q, λ)}

Paso 6… f(q, var, S) = {(q, FNP)} f(q, if, S) = {(q, CTBP), (q, CTBEBP)} f(q, if, B) = {(q, CTB), (q, CTBEB)} f(q, var, B) = {(q, FN)} f(q, cond, C) = {(q, λ)} f(q, ::=, F) = {(q, λ)} f(q, num, N) = {(q, λ)} f(q, ;, P) = {(q, λ)} f(q, then, T) = {(q, λ)} f(q, else, E) = {(q, λ)}

F N P

if

cond

then

var

::=

num

;

N P

if

cond

then

var

::= num

;

Paso 7… f(q, var, S) = {(q, FNP)} f(q, if, S) = {(q, CTBP), (q, CTBEBP)} f(q, if, B) = {(q, CTB), (q, CTBEB)} f(q, var, B) = {(q, FN)} f(q, cond, C) = {(q, λ)} f(q, ::=, F) = {(q, λ)} f(q, num, N) = {(q, λ)} f(q, ;, P) = {(q, λ)} f(q, then, T) = {(q, λ)} f(q, else, E) = {(q, λ)}

if

cond

then

P

var

::=

num

;

Pila vacía Sentencia reconocida Para una transición: Representaremos con: (a, b,...) los elementos de Σ (A, B, C..) los de Γ (x, y, z,...) los de Σ* (X, Y, Z,...) los de Γ* La interpretación de f es: 𝑓(𝑞. 𝑎, 𝐴) = {(𝑞1, 𝑍1 ), (𝑞2, 𝑍2 ), . . (𝑞𝑛 , 𝑍𝑛 )} - 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. 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; el autómata pasará a algún estado 𝑞𝑖 (recordar que es

no determinista), eliminará el símbolo A de la pila e introducirá en ella la palabra 𝑍𝐼 , quedando la cabeza de 𝑍𝑖 en la cima de la pila. - Paso 2: El autómata pasará a algún estado 𝑞1 , eliminará el símbolo A de la pila e introducirá en ella la palabra 𝑍𝑖 , quedando la cabeza de 𝑍𝑖 en la cima de la pila. Cuando el autómata se encuentra en el estado q, y tiene el símbolo A en la cima de la pila; el autómata pasará a algún estado 𝑞𝑖 (recordar que es no determinista), eliminará el símbolo A de la pila e introducirá en ella la palabra 𝑍𝑖 , quedando la cabeza de 𝑍𝐼 en la cima de la pila.

𝑓(𝑞, λ, A) = {(𝑞1 , 𝑍1 ), (𝑞2 , 𝑍2 ), … (𝑞𝑛 , 𝑍𝑛 )} - Paso 3: El procedimiento se repite n veces Se entiende que el resultado de la función f para las configuraciones (estado, símbolo de entrada y símbolo de pila) no explícitamente especificadas es el conjunto vacío. Estas representan configuraciones “muertas” del autómata. Apoyándose en el simulador JFlap o VAS ejecutar y validar por lo menos cinco cadenas válidas y 5 cadenas rechazadas por el autómata. En este espacio adjunta la imagen.

Practicar y verificar lo aprendido

Cinco (5) Cadenas Validas AAB y BBA (Alfabeto) – En los estados q0, q1, q2, q3