AUTOMATAS Y LENGUAS FORMALES

TAREA 3 – CONSTRUCIÓN AUTOMATA DE PILA

Presentado por:

IVAN CAMILO APONZA CANTOÑI

Código: 1061431816
ROBINSON ALEXANDER ACOSTA VELASCO
Código: 1013657837
LINA MARCELA CERON PEREZ
CÓDIGO: 1.235.338.073
JULIO CESAR CORRALES
CÓDIGO: 1065596376

Presentado a:

Tutor: JAIME JOSE VALDES

Grupo: 301405_47

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA –UNAD

ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA –ECBTI

INGENIERÍA DE SISTEMAS

ABRIL de 2021
 Estudiante Ivan Camilo Aponza

Ejercicios 1: Autómata de Pila

EJERCICIO A
TRABAJAR

Caracterización SÉTUPLA DEL AUTOMATA

del autómata a
pila 𝑨𝑷 = (𝚺, 𝚪, 𝐐, 𝐀𝟎, 𝐪𝟎, 𝐅, 𝐟)

∑ = {0,1,}
r = {Z, A, AA, 𝜆 ,B}
Q = {q0, q1}
A0 = 𝜆
𝒒𝟎 ⋲ 𝑸 = q0
𝑭 ⊆ 𝑸 = {q1}
𝑓:
σ = (𝑞0,0, 𝑍), (𝑞0, 𝐴)
σ = (𝑞0,0, 𝐴), (𝑞0, 𝐴𝐴)
σ = (𝑞0,1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1,0, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1, 1, 𝐴), (𝑞1, 𝐵)

CUADRO COMPARATIVO
AP VACIADO POR AP VACIADO POR ESTADO FINAL
PILA
 𝑃 = (𝑄, Σ, Γ, 𝛿. 𝑞0 , 𝑧0 )  ⊢∗𝑃 : se puede llegar a través de P
El lenguaje aceptado por P con 0 o más pasos. Donde:
por pila vacía es
𝑃 = (𝑄, Σ. ⏟
Γ , 𝛿, 𝑞0 ,
𝑁(𝑃) = {𝑊|(𝑞0 , 𝑤, 𝑧0 ) ⊢∗𝑃 (𝑞, 𝑆𝑖𝑚𝑏𝑜𝑙𝑜 𝑑𝑒 𝑙𝑎 𝑝𝑖𝑙𝑎

⋋,⋋)} 𝑧⏟0 ,𝐹
𝑆𝑖𝑚𝑏𝑜𝑙𝑜 𝑑𝑒 𝑙𝑎 𝑝𝑖𝑙𝑎 𝑣𝑎𝑐𝑖𝑎

Al reconocer por pila vacía,

la pila se queda vacía del el lenguaje aceptado por P por estado
todo, sin Zo. final es

𝐿(𝑃) = {𝑤|(𝑞0, 𝑤, 𝑧0 ) ⊢∗𝑃 (𝑞,⋋, 𝑦), 𝑞 ∈ 𝐹}

  Antes de diseñar un AP, hay que
 Si existe un AP P que reconoce decir si queremos que acepte por
un lenguaje por estado final, estado final o por pila vacía, pues el AP
entonces existe otro AP P ' que deberá ser distinto.
reconoce el mismo lenguaje por
pila vacía: L(P) = N(P’)
 En esta aceptación, luego de la
palabra leída en la cinta el estado de la
En esta aceptación, luego de pila no necesariamente vacía
la palabra leída en la cinta el
estado de la  De estado final a pila vacía: Dado
pila
necesariamente vacía. un autómata a pila PF que acepta un
lenguaje L por estado final, se
construye otro autómata a pila P N
Para cada autómata que acepte que acepta L por pila vacía.
cadenas sin vaciar su pila, existe
un autómata equivalente pero Ejemplo:
que vacía su pila antes de llegar 𝑳𝟑 = {𝟎𝒏 𝟏𝒎 | 𝒏 > 𝒎}
a un estado de aceptación.

De pila vacía a estado final: El

conjunto de los lenguajes que
son aceptados por algún
autómata a pila por estado final
es el mismo que el conjunto de
los lenguajes que son aceptados
por algún autómata a pila por
vaciado de pila.
Ejemplo:

𝑳𝟑 = {𝟎𝒏 𝟏𝒎 | 𝒏 > 𝒎}

Procedimiento Para comprobar el funcionamiento del automata vamos a utilizar la cadena

de paso a paso
del recorrido
de una cadena
 {0,0,0,1,1,0}

CINTA DE ENTRADA
0 0 0 1 1 0
PILA
TRANSICIONES
σ = (𝑞0,0, 𝑍), (𝑞0, 𝐴)
σ = (𝑞0,0, 𝐴), (𝑞0, 𝐴𝐴)
σ = (𝑞0,1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1, 1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1,0, 𝐴), (𝑞1, 𝐵) Zo
Memoria Auxiliar
MECANISMO DE CONTROL
q0 q1
Paso 1: Estando en el estado inicial q0 se aplica el símbolo de entrada 0, desapila Z
continúa en el mismo estado y apila el valor A.
CINTA DE ENTRADA
0 0 0 1 1 0
PILA
TRANSICIONES
σ = (𝑞0,0, 𝑍), (𝑞0, 𝐴)
σ = (𝑞0,0, 𝐴), (𝑞0, 𝐴𝐴)
σ = (𝑞0,1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1, 1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1,0, 𝐴), (𝑞1, 𝐵) A
Memoria Auxiliar
MECANISMO DE CONTROL
q0 q1

Paso 2: Se repite el Paso 1

CINTA DE ENTRADA
0 0 0 1 1 0
PILA
TRANSICIONES
σ = (𝑞0,0, 𝑍), (𝑞0, 𝐴)
σ = (𝑞0,0, 𝐴), (𝑞0, 𝐴𝐴)
σ = (𝑞0,1, 𝐴), (𝑞1, 𝜆)
A
σ = (𝑞1, 1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1,0, 𝐴), (𝑞1, 𝐵) A
Memoria Auxiliar
MECANISMO DE CONTROL
q0 q1

Paso 2: Estando en el estado inicial q0 se aplica el símbolo de entrada 0, desapila A

continúa en el mismo estado y apila el valor A
 CINTA DE ENTRADA
0 0 0 1 1 0
PILA
TRANSICIONES
σ = (𝑞0,0, 𝑍), (𝑞0, 𝐴)
σ = (𝑞0,0, 𝐴), (𝑞0, 𝐴𝐴) A
σ = (𝑞0,1, 𝐴), (𝑞1, 𝜆)
A
σ = (𝑞1, 1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1,0, 𝐴), (𝑞1, 𝐵) A
Memoria Auxiliar
MECANISMO DE CONTROL
q0 q1

Paso 3: Estando en el estado inicial q0 se aplica el símbolo de entrada 1, desapila el

valor A, pasa al estado q1 y no apila ningún valor
CINTA DE ENTRADA
0 0 0 1 1 0
PILA
TRANSICIONES
σ = (𝑞0,0, 𝑍), (𝑞0, 𝐴)
σ = (𝑞0,0, 𝐴), (𝑞0, 𝐴𝐴)
σ = (𝑞0,1, 𝐴), (𝑞1, 𝜆)
A
σ = (𝑞1, 1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1,0, 𝐴), (𝑞1, 𝐵) A
Memoria Auxiliar
MECANISMO DE CONTROL
q0 q1

Paso 4: Estando en el estado inicial q1 se aplica el símbolo de entrada 1, desapila A

continúa en el mismo estado y no apila ningún valor.

CINTA DE ENTRADA
0 0 0 1 1 0
PILA
TRANSICIONES
σ = (𝑞0,0, 𝑍), (𝑞0, 𝐴)
σ = (𝑞0,0, 𝐴), (𝑞0, 𝐴𝐴)
σ = (𝑞0,1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1, 1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1,0, 𝐴), (𝑞1, 𝐵) A
Memoria Auxiliar
MECANISMO DE CONTROL
q0 q1

Paso 5: Estando en el estado inicial q1 se aplica el símbolo de entrada 0, desapila A

continúa en el mismo estado y apila el valor B.
 CINTA DE ENTRADA
0 0 0 1 1 0
PILA
TRANSICIONES
σ = (𝑞0,0, 𝑍), (𝑞0, 𝐴)
σ = (𝑞0,0, 𝐴), (𝑞0, 𝐴𝐴)
σ = (𝑞0,1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1, 1, 𝐴), (𝑞1, 𝜆)
σ = (𝑞1,0, 𝐴), (𝑞1, 𝐵) B
Memoria Auxiliar
MECANISMO DE CONTROL
q0 q1
Practicar y
verificar lo
aprendido

Lenguaje AP = ({0,1},{Z, A, AA, 𝜆 , B}, {q0, q1}, 𝜆, {q0}, δ, { q1})

regular
Ejercicio 2: Gramática del autómata
𝒒𝟎 → 𝟎𝒒𝟎 | 𝟏𝒒𝟏
𝒒𝟏 → 𝟏𝒒𝟏 |𝟎𝒒𝟏
𝒒𝟏 → 𝟎

Estudiante Robinson Alexander Acosta

Ejercicios 1: Autómata de Pila

EJERCICIO A
TRABAJAR

Séptupla del autómata

CARACTERIZACIÓN AP = (Σ, Γ, Q, A0, q0, f, F)

DEL AUTÓMATA A
PILA Σ = {𝑎, 𝑏}
𝜞 = {𝜆, 𝑎}
𝑸 = {𝑞0, 𝑞1}
𝑨𝟎 = {𝜆}
𝒒𝟎 € 𝑸 = 𝑞0
𝑭 ⊆ 𝑸 = {𝑞1}
𝒇: ơ = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎)
ơ = (𝑞0, 𝑏, 𝑎), (𝑞1, 𝜆)
ơ = (𝑞1, 𝑏, 𝑎), (𝑞1, 𝜆)

Para el desarrollo de este paso, utilizaremos la cadena:

aaabba

PROCEDIMIENTO
DE PASO A PASO
DEL RECORRIDO CINTA DE ENTRADA
DE UNA CADENA a a a b b a

TRANSICIONES
ơ = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎)
ơ = (𝑞0, 𝑏, 𝑎), (𝑞1, 𝜆)
ơ = (𝑞1, 𝑏, 𝑎), (𝑞1, 𝜆)
𝑍0
MECANISMO DE CONTROL PILA

Paso 1:
Cuando el autómata se encuentra en el estado inicial q0, lee el
símbolo de entrada a, no elimina nada de la pila y apila o
introduce el símbolo a en la pila
CINTA DE ENTRADA
a a a b b a

TRANSICIONES
ơ = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎)
ơ = (𝑞0, 𝑏, 𝑎), (𝑞1, 𝜆)
A
ơ = (𝑞1, 𝑏, 𝑎), (𝑞1, 𝜆)
𝑍0

MECANISMO DE CONTROL PILA

Paso 2:
Como en la cinta de entrada se repite el mismo símbolo a, del paso
anterior se realiza el mismo procedimiento y apilamos otra a, en la
pila

CINTA DE ENTRADA
a a a b b a

TRANSICIONES
ơ = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎) A
ơ = (𝑞0, 𝑏, 𝑎), (𝑞1, 𝜆)
A
ơ = (𝑞1, 𝑏, 𝑎), (𝑞1, 𝜆)
𝑍0

MECANISMO DE CONTROL PILA

Paso 3:
Como en la cinta de entrada se repite el mismo símbolo a, del paso
anterior se realiza el mismo procedimiento y apilamos otra a, en la
pila
CINTA DE ENTRADA
a a a b b a

TRANSICIONES A
ơ = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎) A
ơ = (𝑞0, 𝑏, 𝑎), (𝑞1, 𝜆)
A
ơ = (𝑞1, 𝑏, 𝑎), (𝑞1, 𝜆)
𝑍0

MECANISMO DE CONTROL PILA

Paso 4:
El automata se encuentra en el estado inicial q0, lee el simbolo
de entrada b, elimina el simbolo a de la pila, pasa al estado final
q1 y no introduce nada en la pila
CINTA DE ENTRADA
a a a b b a

TRANSICIONES A
ơ = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎)
A
ơ = (𝑞0, 𝑏, 𝑎), (𝑞1, 𝜆)
ơ = (𝑞1, 𝑏, 𝑎), (𝑞1, 𝜆) 𝑍0

MECANISMO DE CONTROL PILA

Paso 5:
El automata se encuentra en el estado final q1, lee el simbolo
de entrada b, elimina de la cinta el simbolo a y no introduce
nda en la pila
 CINTA DE ENTRADA
a a a b b a

TRANSICIONES
ơ = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎)
A
ơ = (𝑞0, 𝑏, 𝑎), (𝑞1, 𝜆)
ơ = (𝑞1, 𝑏, 𝑎), (𝑞1, 𝜆) 𝑍0

MECANISMO DE CONTROL PILA

Paso 6:
Como en la cinta se encuentra el simbolo de entrada a, el
automata no lee nada y finaliza su recorrido.

PRACTICAR Y
VERIFICAR LO
APRENDIDO
LENGUAJE 𝑨𝑷 = ({𝒂, 𝒃}, {𝜆, 𝒂 }, {𝒒𝟎, 𝒒𝟏}, 𝝀, {𝒒𝟎}, 𝜹, {𝒒𝟏})
REGULAR
EJERCICIO 2 GRAMATICA DEL AUTOMATA

𝑅 = {𝑆 → (𝑠, 𝑖 𝑓), 𝑓 𝐸 𝑓)
𝑈 {𝑓, 𝑖, 𝑓} → 𝐸, 𝑓 𝐸 𝐹}
𝑈 {(𝑝, 𝐸, 𝑝) → 𝐸, 𝑝 𝐸 𝐾}
𝑈 {(𝑝, 𝐴, 𝑟) → 𝑥(𝑞, 𝐸, 𝑟), ((𝑝, 𝑥, 𝐴), (𝑞, 𝐸)) 𝐸 ∆, 𝑒 𝐸 𝐾}
𝑈 {(𝑝, 𝐴, 𝑟) → 𝑥(𝑞, 𝐵1, 𝑟1) (𝑟1, 𝐵2, 𝑟2) … (𝑟𝑘 − 1, 𝐵𝑘, 𝑟)
(𝑝, 𝑥, 𝐴), (𝑞, 𝐵1𝐵2 … 𝐵𝑘)) 𝐸∆, 𝑟1, 𝑟2, … . 𝑟𝑘 − 1, 𝑟 𝐸 𝐾}

Regla inicial = s→ (q0, λ, q1)

Regla N° 1 = (q1, λ, q1) → λ
Regla N° 2 = (q0, λ, q0) → λ
Regla N°3 = (q1, λ, q0) → λ
Regla N°4 = (q0, a, q0) → b (q1, λ, q0)
Regla N°5 = (q0, a, q1) → b (q1, λ, q1)
Regla N°6 = (q1, a, q0) → b (q1, λ, q0)
Regla N°7 = (q1, a, q1) → b (q1, λ, q1)
Regla N°8 = (q0, λ, q0) → a (q0, a, q0) (q0, λ, q0)
Regla N° 9 = (q0, λ, q1) → a (q0, a, q1) (q0, λ, q1)
Regla N°10 = (q0, a, q0) → a (q0, a, q0) (q0, a, q0)
Regla N°11 = (q0, a, q1) → a (q0, a, q1) (q0, a, q1)

GRAMATICA POR IZQUIERDA

PALABRA O CADENA A LEER: abbb

Partimos desde la regla inicial

s→ (q0, λ, q1)

 Buscamos en las reglas la que me permita leer a, en este caso utilizaremos la regla
N° 9

a (q0, a, q0) (q0, λ, q1)

 Para la lectura del siguiente símbolo b, utilizaremos la lectura de la regla N°4,
obteniendo:

ab (q1, λ, q0) (q0, a, q1)

 Para la lectura del siguiente símbolo b, utilizaremos la regla N°3 para eliminar (q1, λ,
q0), obteniendo

ab (q0, a, q1)

En este paso utilizare la regla N°5 para, para la lectura de b

abb (q1, λ, q1) (q0, a, q1)

Ahora utilizare la regla N°1 para eliminar (q1, λ, q1) en la lectura anterior, obteniendo:

abb (q0, a, q1)

 Para la lectura del siguiente símbolo b, utilizaremos la regla N°5, obteniendo:

abbb (q1, λ, q1)

Para finalizar con la lectura de la palabra, utilizare la regla N°1 para eliminar (q1,
λ, q1) en la lectura anterior, obteniendo:

abbb

Estudiante Lina Marcela Cerón

Ejercicios B: Autómata de Pila

EJERCICIO A
TRABAJAR

Caracterización En este espacio se realiza:

del autómata a Mediante la definición formal explicar las características del autómata
pila
Σ =Alfabeto de entrada
Γ =Alfabeto de salida
Q =conjunto finito de estados
A0 ∈ Γ = símbolo inicial de la pila
q0 ∈ Q = estado inicial del autómata
F ⊆ Q = estado final del autómata
F= función de transiciones de ternas

AP= (Σ, Γ, Q, A0, q0, f, F)

Σ= {a, b, λ}
Γ = {λ, a, b}
Q = {q0, q1}
A0 = ʎ
q0 ∈ Q = q0
F ⊆ Q = q1
Funciones de transición

ơ = (qo, b, ʎ), (q0, b)

ơ = (qo, a, ʎ), (q0, a)

ơ = (q0, ʎ, ʎ), (q1, ʎ)

ơ = (q1, a, a), (q1, ʎ)

ơ = (q1, b, b), (q1, ʎ)

- Realizar un cuadro comparativo de la Equivalencia entre AP por

vaciado de pila y AP por estado final

Ap por estado Final Ap por vaciado

Lenguaje reconocido Lenguaje reconocido
(Ejemplo) (Ejemplo)
LF(AP) = {x | (q0, x, A0) * (p, λ, LV(AP) = { x | (q0, x, A0) * (p,
X), con p ∈ F, X∈Γ*} λ, λ) con p ∈ Q}
Si el autómata a pila por estado Si el autómata a pila por vaceado
final reconoce el mismo lenguaje reconoce el mismo lenguaje que el
que el autómata por vaciado autómata por estado final
entonces son equivalentes entonces son equivalentes

Se dos autómatas a pila ya sea por vaciado de pila o por estado final son
equivalentes si aceptan el mismo lenguaje.
Un autómata a pila 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: LV(AP) = {x | (q0, x, A0) * (p, λ, λ) con p ∈ Q}

donde LF(AP) y LV(AP) representan a los lenguajes reconocidos por el

autómata AP por estado final y por vaciado de pila respectivamente.

Si la aceptación es por vaciado de pila, el conjunto de estados finales F es

irrelevante
Procedimiento Realice de manera detallada y grafica el procedimiento paso a paso del
de paso a paso recorrido de una cadena (La cadena la selecciona el estudiante, debe
del recorrido de contener como mínimo 8 caracteres) en el autómata a pila. Describir
una cadena cómo funciona el almacenamiento en la pila, como funciona LIFO, etc.

Autómata a pila

Este autómata de pila tiene la cienta de entrada, la memoria de la pila

para el apile y el desapile y a la izquierda e incluido las funciones de
transición

Paso 1
Comenzamos la primera función de transición, hacemos la lectura de b
con la primera transición la cual está en q0 y se dirige hacia q0 y se apila
una b

Paso 2

Pasamos a la siguiente transición donde no se desapila nada y se apila

una a

Paso 3

Aquí la entrada esta vacía y siempre que la entrada este vacía se cumple
la regla de entrada por lo que no se desapila nada y tampoco se apila,
pero si se pasa de q0 a q1
Paso 4

En la cuarta función de transición nos encontramos ya en el estado q1 y

como la entrada es una a se desapila una a y no se apila nada

Paso 5

En la quinta función de transición al ser la entrada b se desapila una b y

no se apila nada
 Finaliza la lectura del autómata con una aceptación llegando a q1 y la
memoria de la pila vacía
os autómatas de pila cuentan con una memoria auxiliar llamada pila. Los
símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de
la pila, de acuerdo con el manejo last-in-first-out (LIFO)
Para manejar dichos datos hay 2 operaciones esenciales que son apilar
(push), que no es más que colocar un objeto en la pila, y retirar (o desapilar,
pop), que sería su operación inversa ya que retira el último elemento
apilado.

Practicar y
verificar lo
aprendido

EJERCICIO 2 GRAMATICA DEL AUTOMATA

Gramática del autómata El estudiante realiza paso a paso la gramática del autómata que seleccionó.

Identifique su gramática (de forma manual) por la derecha o izquierda y la caracteriza. Debe incluir

el diagrama de estados con los componentes de la gramática asociados a las variables y a las

constantes.

Basándonos en esto comenzaremos a desarrollar la gramática del autómata

Estas son las reglas principales en las cuales nos vamos a basar.
R = {S →(s, i f), f E f)
U {f, i, f} → E, f E F}
 U {(p, E, p) → E, p E K}
U {(p, A, r) → x(q, E, r), ((p, x, A), (q, E)) E ∆, e E K}
U {(p, A, r) → x(q,B1, r1) (r1, B2, r2)…(rk-1, Bk, r)
((p, x, A), (q, B1B2…Bk)) E∆, r1, r2,…. rk-1,r
E K}
Este conjunto de reglas asume que S es el no terminal inicial, y será el mismo alfabeto,
que el autómata con pila, el conjunto F es el conjunto de estados finales El estado s es el estado
inicial, el conjunto k es el conjunto de estados y el conjunto delta es el conjunto de transiciones.
Con eso en mente vamos a armar nuestras reglas.
La regla inicial se arma con el estado inicial, el símbolo de fin de pila y el estado
final, esto se repite por cuantos estados finales tengamos en este caso solo es 1.

R = S →(q0, λ,q1)

En el segundo paso tenemos una regla por cada estado final por lo tanto
escribimos estado final, símbolo de desapile y el estado final.

(q1, λ, q1) → λ
En la próxima regla vamos a tener tantas de estas reglas como estados tengamos en el
autómata.

(q1, λ, q1) → λ
(q0, λ, q0) → λ
(q1, λ, q0) → λ
(q0, λ, q1) → λ

(q0, b, q0) → b (q1, λ, q0)

(q0, b, q1) → b (q1, λ, q1)
(q1, b, q0) → b (q1, λ, q0)
(q1, b, q1) → b (q1, λ, q1)

(q0, a, q0) → a (q1, λ, q0)

(q0, a, q1) → a (q1, λ, q1)
(q1, a, q0) → a (q1, λ, q0)
(q1, a, q1) → a (q1, λ, q1)

(q0, λ, q0) → a (q0, a, q0) (q0, λ, q0)

(q0, λ, q1) → a (q0, a, q0) (q0, λ, q1)
(q0, λ, q0) → b (q0, b, q0) (q0, λ, q0)
(q0, λ, q1) → b (q0, b, q0) (q0, λ, q1)
(q0, a, q0) → b (q0, b, q0) (q0, a, q0)
(q0, a, q1) → b (q0, b, q0) (q0, a, q1)
(q0, b, q0) → a (q0, a, q0) (q0, b, q0)
(q0, b, q1) → a (q0, a, q0) (q0, b, q1)
Ahora que tenemos las reglas realizamos la lectura de izquierda a
derecha Usamos la siguiente palabra:
baa

Entonces iniciamos desde la regla inicial

R = S →(q0, λ,q1)
El primer paso es seleccionar una regla que se asemeje a la regla inicial, en este
caso es:

(q0, λ, q1)

Se hace uso de esta regla

b (q0, b, q0) (q0, a, q0)
Hacemos lectura de la siguiente regla
a (q1, λ, q0)
y usamos la letra nula en esa regla para reemplazar la primera de las reglas y
obtener la lectura de la letra a
ba (q1, λ, q0)(q0, b, q1)
ba (q0,b, q1)

y para la a restante uso la 7 regla

quedando así
baa (q1, λ, q1) (q0, b, q1)

Luego eliminamos las reglas

correspondientes y quedamos con la

palabra final
baa
JULIO CESAR CORRALES

Ejercicios 1: Autómata de Pila

Ejercicio a trabajar

Caracterización del Identificación de la séptupla del autómata:

autómata a pila - Q = {q0, q1}
- ∑ = {0,1}
- r = {𝜆,B,C,BC,Z}
- A0 = B
- q0 ∈ 𝑄 = {q0} Estado inicial
- f = No hay estado final
- δ = transiciones

Cuadro de transiciones

Transiciones
(q0, 0, Z), (q0, B)
(q0, 0, C), (q0, BC)
(q0, 0, B), (q0, C)
(q0, 1, C), (q1, 𝜆)
(q1, 1, C), (q1, 𝜆)

Cuadro comparativo
AP por vaciado de pila AP por estado final
Posee estados, transiciones y Igualmente que el vaciado de
alfabeto, en este método el pila este posee estados,
autómata intenta vaciar la pila transiciones y alfabeto, pero
luego de examinarla la única forma de que este
completamente ignorando en autómata sea aceptado es
qué estado va a finalizar pero que luego de ser analizado se
aun asi depende de la encuentre en un estado de
información de la pila. aceptación, aunque esa
cadena no dependa de la
información de la pila.
Procedimiento de paso a Podemos evidenciar la cadena correcta haciendo uso de la
paso del recorrido de una aplicación JFLAP que nos permite revisar dichos procesos
cadena como se verá a continuación.
Paso 1

Paso 2

Paso 3
Paso 4

Paso 5
Paso 6

Paso 7

Paso 8
Lenguaje regular {0*.1.1*}

Ejercicios 2: Gramática del autómata

El estudiante realiza paso a paso la gramática del autómata que seleccionó.

Identifique su gramática (de forma manual) por la derecha o izquierda y la caracteriza.

Debe incluir el diagrama de estados con los componentesde la gramática asociados a
las variables y a las constantes.

Gramática:

S => 0S
S => 1A
A => 1A

Árbol de derivación:
 Ejercicio Grupal: Minimización de autómatas

EJERCICIO A
TRABAJAR

PROCESO DE
MINIMIZACIÓN Primero clasificamos los estados en 2 conjuntos, los estados finales y los
que no lo son.
𝐴 = {𝑞4, 𝑞6}
𝐵 = {𝑞0, 𝑞1, 𝑞2, 𝑞3, 𝑞5}

Ahora creamos tablas de transiciones para ver si hay equivalenciar y crear

nuevos conjuntos
A 0 1
q4 B
q6 B B

Como podemos ver en el primer conjunto no hay equivalentes entre q4 y

q6.
B 0 1
q0 A B
q1 A B
q2 B A
 q3 A B
q5 B A

Como podemos ver, en el segundo conjunto q0, q1 y q3 son equivalentes.

Tambien q2 y q5 son equivalentes.
Creamos los nuevos conjuntos teniendo en cuenta las equivalencias.

𝐴 = {𝑞4}
𝐵 = {𝑞6}
𝐶 = {𝑞0, 𝑞1, 𝑞3}
𝐷 = {𝑞2, 𝑞5}

Ahora creamos de nuevo las tablas de transiciones para buscar

equivalencias y crear nuevos conjuntos

A 0 1
q4 D

B 0 1
q6 D C

Los estados q4 y q6 no son equivalentes

C 0 1
q0 B C
q1 B D
q3 D B

D 0 1
q2 B C
q5 D B

Los estados q0 y q2 son equivalentes, igualmente q3 y q5 son

equivalentes.

Creamos los nuevos conjuntos teniendo en cuenta las equivalencias.

𝐴 = {𝑞4}
𝐵 = {𝑞6}
𝐶 = {𝑞0, 𝑞2}
𝐷 = {𝑞1}
𝐸 = {𝑞3, 𝑞5}

Ahora creamos de nuevo las tablas de transiciones para buscar

equivalencias y crear nuevos conjuntos.

A 0 1
q4 C

B 0 1
q6 E E

C 0 1
q0 A D
q2 A E

D 0 1
q1 A E

E 0 1
q3 E A
q5 E A

Los estados q1 y q2 son equivalentes, igualmente q3 y q5 son

equivalentes.

Creamos los nuevos conjuntos teniendo en cuenta las equivalencias.

𝐴 = {𝑞4}
𝐵 = {𝑞6}
𝐶 = {𝑞0}
𝐷 = {𝑞1, 𝑞2}
𝐸 = {𝑞3, 𝑞5}
 Ahora creamos de nuevo las tablas de transiciones para buscar
equivalencias y crear nuevos conjuntos

A 0 1
q4 D

B 0 1
q6 E E

C 0 1
q0 A D

D 0 1
q1 A E
q2 A E

E 0 1
q3 E A
q5 E A

En cada tabla de transicion hay equivalencias. Ahora teniendo en

cuentalos nuevos estados creamos la tabla de transicion del automata
minimizado.

0 1
A D
B E E
C A D
D A E
E E A
Resultado de
Autómata
minimizado
 𝐴 = ({𝐴, 𝐵, 𝐶, 𝐷, 𝐸}, {0,1}, 𝛿, 𝐷, {𝐸, 𝐴}), 𝑑𝑜𝑛𝑑𝑒:
𝑄 = {𝐴, 𝐶, 𝐸}
𝛴 = {0,1}
𝑠= 𝐷
Notación 𝐹 = {𝐸, 𝐴}
formal del 𝛿 = 𝑡𝑟𝑎𝑛𝑠𝑖𝑐𝑖𝑜𝑛𝑒𝑠
autómata
minimizado 𝛿(𝐷, 0) = {𝐴}
𝛿(𝐷, 1) = {𝐸}
𝛿(𝐴, 0) = {𝐷}
𝛿(𝐵, 0) = {𝐸}
𝛿(𝐵, 1) = {𝐸}
𝛿(𝐶, 0) = {𝐴}
𝛿(𝐶, 1) = {𝐷}
𝛿(𝐸, 0) = {𝐸}
𝛿(𝐸, 1) = {𝐴}
Tabla de transición

0 1
D A E
B E E
C A D
#A D -
#E E A
Caracterización
del autómata M = ( {A,B,C,D,E} , {0,1} ,𝛿 ,D, {A, E}) → 5-tupla
parte teórica
K = { A,B,C,D,E } → conjunto finito de estados, Es es un modelo
computacional que realiza cómputos en forma automática sobre una
entrada para producir una salida y tiene un numero contado de estados.
 ∑ = {0,1} → Alfabeto, Es un conjunto finito de símbolos que formarán
palabras o cadenas y su funcion dentro del automata es reconocer los
lenguajes que leera la maquina.

s = D → Estado inicial: Es el estado en qué el autómata se encuentra

inicialmente.

F = A, E → Estado final o aceptación, Es es ultimo estado del automata,

en este estado se evaluaa si hay aceptacion y de igual manera finalizan las
transiciones dentro del mismo.

𝜹 = → Relación de transiciones, Se encarga de determinar el

comportamiento del automata.
Lenguaje
regular 𝑨𝑭 = ({𝐴, 𝐵, 𝐶, 𝐷, 𝐸}, {0,1}, 𝛿, 𝐷, {𝐴, 𝐸})

Gramática del 𝑫 → 𝟎𝑩 | 𝟏𝑫
Autómata 𝑩 → 𝟎𝑬 | 𝟏𝑬
𝑪 → 𝟎𝑨 | 𝟏𝑫
𝑨 → 𝟎𝑫 | 𝟏 𝜆 | 𝜆
𝑨 → 𝟎𝑬 | 𝟏𝑨 | 𝜆

Validación de
cadenas

Practicar y
verificar lo
aprendido
 REFERENCIAS BIBLIOGRAFICAS

Alfonseca Cubero, E. (2007). Teoría de autómatas y lenguajes formales. Madrid etc., Spain:
McGraw-Hill España. (pp. 117 - 150). Recuperado de https://elibro-
net.bibliotecavirtual.unad.edu.co/es/lc/unad/titulos/50119
González, A. [Ángela]. (2017, noviembre 5). Autómatas Finitos. [Archivo de video].
Recuperado de http://hdl.handle.net/10596/10470
González, A. [Ángela]. (2020, julio 14). Lenguajes Regulares. [Archivo web]. Recuperado
de https://campus113.unad.edu.co/ecbti84/mod/hvp/view.php?id=72