Fase2 Individual Hemir Ejercicio4 512t1g

AUTOMATAS Y LENGUAJES FORMALES FASE 2: LENGUAJES INDEPENDIENTES DEL CONTEXTO

Presentado por: HEMIR FIGUEROA COETATA Grupo: 301405_59

Tutor: JAIME JOSE VALDES

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA (UNAD) ECBTI INGENIERIA DE SISTEMAS OCTUBRE 2018

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

Ejercicio

1y9

Ejercicio 1

2y8

Ejercicio 2

3y7

Ejercicio 3

4y6

Ejercicio 4

5y0

Ejercicio 5

El diseño solicitado corresponde al diligenciamiento de la siguiente tabla: Ejercicio 4

EJERCICIO A TRABAJAR

Caracterizació n del autómata a pila

Un autómata a pila es una séptupla: AP= (Σ, Γ, Q, 𝑎0 , 𝑞0 , 𝛿, F) donde: • • • • • • •

Σ es el alfabeto de entrada Γ es el alfabeto de la pila Q es un conjunto finito de estados A0 ∈ Γ es el símbolo inicial de la pila q0 ∈ Q el estado inicial del autómata F ⊆ Q es el subconjunto de estados finales 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: Σ= {A, B, Z} Q= {𝑞0 , 𝑞1 , 𝑞2 , 𝑞3 }} Γ= {Z}

Un AP puede reconocer palabras del alfabeto de entrada de dos formas distintas:

por estado final: -

Lf(AP) = {x | (q0, x, A0) ├* (p, λ, X), con p∈F, X∈Γ*} por vaciado de pila:

Procedimiento de paso a paso del recorrido de una cadena

- LV(AP) = { x | (q0, x, A0) ├* (p, λ, λ) con p∈Q} El autómata solo acepta 2 cadenas: B, AAB.

Por tanto: Tomamos del alfabeto de entrada A y B para agregar a la pila. Se tiene la pila con una z y se procede a realizar las transiciones.

Gráficamente al iniciar la secuencia.

Agregada la primera transición.

Agregada otra Z al realizar la transición q1 a q2

Se finaliza la secuencia y aceptada la cadena AAB

Se procede a realizar la segunda cadena B Se inicializa

La pila se encuentra de la siguiente manera

Al correr la cadena se pasa al estado q3.

Y se finaliza la secuencia.

Practicar y verificar lo aprendido

El autómata solo acepta dos cadenas.

BIBLIOGRAFIA



Carrasco, R. Calera, R. Forcada, M. (2016). Teoría de lenguajes, gramáticas y autómatas para informáticos. Recuperado de http://bibliotecavirtual.unad.edu.co:2139/eds/ebookviewer/ebook ?sid=cc916aa0-d5c1-471e-a5a9-34bcb965c705%40pdc-vsessmgr06&ppid=pp_Cover&vid=0&format=EB



Hernández, R. (2010). Practique la teoría de autómatas y lenguajes formales. (pp. 1-124). Recuperado de https://bibliotecavirtual.unad.edu.co:2538/lib/unadsp/reader.actio n?docID=3199845&ppg=10



Alfonseca C, E., Alfonseca M, M., Mariyón S, R. (2009). Teoría de autómatas y lenguajes formales. Recuperado de https://bibliotecavirtual.unad.edu.co:2538/lib/unadsp/reader.actio n?docID=3195129&ppg=6.