Ricardomolanoluna Grupo 301405 35
-
Rating
-
Date
May 2018 -
Size
695.1KB -
Views
294 -
Categories
Transcript
AUTOMATAS Y LENGUAJES FORMALES
UNIDADES 1, 2, 3 – TRABAJO FINAL
Presentado a la Ingeniera:
Helena Clara Isabel Alemán
Presentado por:
Ricardo Molano Luna
Código: 76 326 256
Grupo:
301405_35
Universidad Nacional Abierta y a Distancia UNAD
Escuela de Ciencias Básicas e Ingeniería
Diciembre2017
Desarrollo de la Actividad
Ejercicio 1:
De cada uno de los siguientes autómatas, realizar el procedimiento paso a
paso de hallar la expresión regular, el lenguaje regular y explicar el tipo de
autómata que es:
1.
Expresión Regular
x =rx+s
x =r∗s 𝑆
= 𝑎𝑞0 + 𝑏𝑞2 𝐵
= 𝑎𝑞2 + 𝑏𝑞1 𝐴
= 𝑎𝑞1 + 𝑏𝑞1 + ʎ 𝐴
= 𝑎𝑞1 + 𝑏𝑞1 + ʎ 𝐴
= (𝑎 + 𝑏) 𝑞2 + ʎ 𝐴
= (𝑎 + 𝑏)∗ 𝐵
= 𝑎𝑞2 + 𝑏𝑞1 𝐵
= 𝑎∗ (𝑏(𝑎 + 𝑏)∗ ) 𝑆
= 𝑎𝑞0 + 𝑏𝑞2 𝑆
= 𝑎∗ (𝑏(𝑎∗ (𝑏(𝑎 + 𝑏)∗ )))
Expresión regular: 𝐸𝑅
= 𝑎∗ (𝑏(𝑎∗ (𝑏(𝑎|𝑏)∗ )))
Lenguaje regular: 𝐿
𝑤 ∈ {𝑎, 𝑏} ∗ |𝜔 = 𝑡𝑜𝑑𝑎𝑠 𝑙𝑎𝑠 𝑐𝑎𝑑𝑒𝑛𝑎𝑠 𝑞𝑢𝑒 𝑒𝑚𝑝𝑖𝑒𝑛𝑧𝑒𝑛 𝑝𝑜𝑟 𝑢𝑛𝑎 a 𝑜 𝑝𝑜𝑟 𝑚𝑢𝑐ℎ𝑎𝑠 𝑎,
={ }
𝑠𝑒𝑔𝑢𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑢𝑛𝑎 𝑏, 𝑠𝑒𝑔𝑢𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑢𝑛𝑎 𝑎 𝑜 𝑚𝑢𝑐ℎ𝑎𝑠 𝑎 𝑦 𝑞𝑢𝑒 𝑡𝑒𝑟𝑚𝑖𝑛𝑒𝑛 𝑒𝑛 𝑢𝑛𝑎 𝑎 𝑜 𝑏 𝑜 𝑚𝑢𝑐ℎ𝑎𝑠 𝑎 𝑦 𝑏
Tipo de autómata
Es un autómata finito no determinista ya que es un autómata que tiene
transiciones por un símbolo de entrada desde un estado de origen y existe más
de una transición posible.
2:
Expresión Regular
x =rx+s
x =r∗s
A = q0 = 1q0 + 0q1
B = q1 = 1q0 + 0q2
S = q2 = 1q0 + 0q2 + ʎ
S = q2 = 1q0 + 0q2 + ʎ 𝑆
= 𝑞2 = (1 + 0)𝑞2 + ʎ 𝑆
= 𝑞2 = (1 + 0)∗
B = q1 = 1q0 + 0q2 𝐵
= 𝑞1 = 1∗ 0(𝑞2 ) 𝐵
= 𝑞1 = 1∗ (0(1 + 0)∗ )
A = q0 = 1q0 + 0q1 𝐴
= 𝑞0 = 1∗ 0(𝑞1 ) 𝐴
= 𝑞0 = 1∗ (0(1∗ (0(1 + 0)∗ )))
Expresión regular: 𝐸𝑅
= 1∗ (0(1∗ (0(1|0)∗ )))
Lenguaje regular:
𝑤 ∈ {1,0} ∗ |𝜔 = 𝑡𝑜𝑑𝑎𝑠 𝑙𝑎𝑠 𝑐𝑎𝑑𝑒𝑛𝑎𝑠 𝑞𝑢𝑒 𝑒𝑚𝑝𝑖𝑒𝑛𝑧𝑒𝑛 𝑝𝑜𝑟 𝑢𝑛 1 𝑜 𝑝𝑜𝑟 𝑚𝑢𝑐ℎ𝑎𝑠 1, 𝐿
={ 𝑠𝑒𝑔𝑢𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑢𝑛 0 , 𝑠𝑒𝑔𝑢𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑢𝑛 1 𝑜 𝑚𝑢𝑐ℎ𝑜𝑠 1, 𝑠𝑒𝑔𝑢𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑢𝑛 0 }
𝑦 𝑞𝑢𝑒 𝑡𝑒𝑟𝑚𝑖𝑛𝑒𝑛 𝑒𝑛 𝑢𝑛 0 𝑜 𝑚𝑢𝑐ℎ𝑜𝑠 0
Tipo de autómata
Es un autómata finito no determinista ya que es un autómata que tiene
transiciones por un símbolo de entrada desde un estado de origen y existe más
de una transición posible.
3:
Expresión Regular
x =rx+s
x =r∗s
S = q0 = 0q2 + 1q1
A = q1 = 1q1
B = q2 = 0q1 + Øq3
C = q3 = 1q1
C = q3 = 1q1 𝐶
= 𝑞3 = 1∗
B = q2 = 0q1 + Øq3 𝐵
= 𝑞2 = (0 + ∅)𝑞2 𝐵
= 𝑞2 = (0 + ∅)∗
A = q1 = 1q1 𝐴
= 𝑞1 = 1∗
S = q0 = 0q2 + 1q1 𝑆
= 𝑞0 = (0 + ∅)∗ 1(𝑞1 ) 𝑆
= 𝑞0 = 1∗ (0 + ∅)∗ (1(1∗ ))
Expresión regular: 𝐸𝑅
= 1∗ (0|∅)∗ (1(1∗ ))
Lenguaje regular:
𝑤 ∈ {1,0} ∗ |𝜔 = 𝑡𝑜𝑑𝑎𝑠 𝑙𝑎𝑠 𝑐𝑎𝑑𝑒𝑛𝑎𝑠 𝑞𝑢𝑒 𝑒𝑚𝑝𝑖𝑒𝑛𝑧𝑒𝑛 𝑝𝑜𝑟 𝑢𝑛 1 𝑜 𝑝𝑜𝑟 𝑚𝑢𝑐ℎ𝑎𝑠 1, 𝐿
= { 𝑠𝑒𝑔𝑢𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑢𝑛 0 𝑜 𝑚𝑢𝑐ℎ𝑜𝑠 0 𝑠𝑒𝑔𝑢𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑐𝑎𝑑𝑒𝑛𝑎 𝑣𝑎𝑐𝑖𝑎, 𝑠𝑒𝑔𝑢𝑖𝑑𝑎𝑠 𝑝𝑜𝑟 𝑢𝑛 1 }
𝑦 𝑞𝑢𝑒 𝑡𝑒𝑟𝑚𝑖𝑛𝑒𝑛 𝑒𝑛 𝑢𝑛 1 𝑜 𝑚𝑢𝑐ℎ𝑜𝑠 1
Tipo de autómata
Es un autómata finito no determinista ya que es un autómata que tiene
transiciones por un símbolo de entrada desde un estado de origen y existe más
de una transición posible.
Teniendo en cuenta el siguiente autómata realizar los puntos
siguientes:
Ejercicio 2: Realizar la conversión de AFD a AFND o de AFND a AFD según
corresponda:
Es un autómata finito no determinista se realiza la conversión a un autómata
finito determinista.
Tabla de transiciones:
ʎ a b c
𝑸𝟎 𝑄1 𝑄2 𝑄0 𝑄4
𝑸𝟏 ∅ 𝑄1 ∅ ∅
𝑸𝟐 ∅ 𝑄4 𝑄0 ∅
𝑸𝟑 ∅ 𝑄5 𝑄1 , 𝑄4 ∅
𝑸𝟒 𝑄1 𝑄3 ∅ 𝑄0
𝑸𝟓 ∅ 𝑄2 𝑄4 𝑄3
𝑸𝟔 = 𝑸𝟏 , 𝑸𝟒 𝑄1 𝑄1 , 𝑄3 ∅ 𝑄0
𝑸𝟕 = 𝑸𝟏 , 𝑸𝟑 ∅ 𝑄1 , 𝑄5 𝑄4 ∅
Nueva tabla de transiciones:
ESTADO TRANSICIONES
a b c
𝑞0 𝑞2 𝑞0 𝑞4
∗ 𝑞1 𝑞1 Ø Ø
𝑞2 𝑞4 𝑞0 Ø
∗ 𝑞3 𝑞5 𝑞4 , 𝑞1 Ø
∗ 𝑞4 𝑞3 Ø 𝑞0
∗ 𝑞5 𝑞2 𝑞4 𝑞3
∗ 𝑞6 𝑞3 , 𝑞1 Ø 𝑞0
𝑞7 𝑞5 , 𝑞1 𝑞4 Ø
Autómata:
Ejercicio 3
Realice la minimización paso a paso del autómata finito determinista
Tomamos como base el autómata AFD del ejercicio anterior.
Ahora vamos a crear los nuevos conjuntos, el conjunto de los estados finales o
aceptadores y el conjunto de los estados no aceptadores.
Y = {C, D, E, F, H} Estados Aceptadores
X = {A, B, G} Estados No Aceptadores
Ahora pasamos a determinar las iteraciones de los conjuntos, comenzando con
el conjunto de los Estados Aceptadores
a b c
C Y θ X
D Y θ X
E Y Y θ
F X Y Y
H Y Y θ
Ahora encontramos las iteraciones del conjunto de los Estados No Aceptadores
a b c
A X X Y
B Y X Y
G Y X θ
Ahora separamos los conjuntos que contienen iteraciones diferentes en nuevos
conjuntos, y los que contienen iteraciones idénticas en el mismo conjunto,
quedando de la siguiente manera:
Y = {C, D} Z = {E, H} W = {F}
X = {A} P = {B} Q = {G}
Ahora corroboramos nuevamente las iteraciones de los nuevos conjuntos
a b c a b c
C Z θ X } Y E W Y θ } Z
D Z θ X H W Y θ
a b c a b c
F Q Y Z } W A P X Y } X
a b c a b c
P Y X Y } P G Y X θ } Q
Graficamos nuestro nuevo autómata ya minimizado, teniendo en cuenta los
nuevos estados y sus transiciones, el cual nos queda de la siguiente manera:
Ejercicio 4: Realizar el autómata a Pila de L = {(a+b)*}
Para la siguiente cadena: bbbaaaabbbaaabbb
Para la cadena: aaabbbaaabbb
Ejercicio 5: Realizar una máquina de Turing de autoría propia y
realice:
a. Recorra la máquina con al menos una cadena válida
explicando lo sucedido tanto en la cinta como en la secuencia
de entrada.
La cadena ingresada es 10.
Recibe como entrada un 1.
Pasa la cinta a un 0 y se queda en 𝑞0.
Llega a q1 cambiando un 0 por 1 y avanza a la derecha.
Después reemplaza a 1 por 1 y retrocede.
Después reemplaza a 1 por vacío y avanza a la izquierda,
llegando al estado q3.
Después reemplaza a 1 por vacío y avanza a la izquierda
llegando al estado q4.
Después reemplaza a vacío por vacío y avanza a la izquierda
llegando a q5.
Después reemplaza a vació por vació y avanza a la izquierda
llegando a q6 que es el estado aceptador.
b. Identifique una cadena que no sea válida y justifíquela porque
Cadena no valida 001.
Esta cadena es inválida porque no tiene los ceros necesarios
para reemplazar durante su recorrido por los estados.
c. Ejecute el RunTest a una cadena aceptada que tenga la menos
cinco símbolos
d. Identifique en que momento la máquina se detiene.
La máquina se detiene cuando llega al estado de aceptación y
la cabeza de la cinta está sobre un espacio en blanco.
Referencias
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:2051/login.aspx?direct=true&db
=nlebk&AN=318032&lang=es&site=eds-
live&ebv=EB&ppid=pp_Cover
Hernández, R. (2010). Practique la teoría de autómatas y lenguajes
formales. (pp. 1 -124). Recuperado de:
http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?
docID=10566114&ppg=10
Alfonseca, C., Alfonseca, M., Mariyón, S. (2009). Teoría de
autómatas y lenguajes formales. (pp. 7-797). Recuperado de:
http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?
docID=10498456&ppg=6
Millán, J., Antonio J. (2009). Compiladores y procesadores de
lenguajes. (pp. 28-62). Recuperado de:
http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/detail.action?d
ocID=10844351
Ferrando, J.C., and Gregori, V. (2012). Matemática discreta (2a.
ed.). (pp. 207-232). Recuperado de:
http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action?
ppg=260&docID=10751543&tm=1481476339478
Gonzalez, A. (2017). Autómatas Finitos. Recuperado de:
http://hdl.handle.net/10596/10470
CK-12, (2015). Operations with Sets. [OVA]. Recuperado
de: http://www.ck12.org/probability/Operations-with-
Sets/plix/Lets-Roll-the-Dice-
56e1fc1f8e0e0813d4b14128/?referrer=concept_details.
CK-12, (2015). Operations with Sets Practice. [OVA]. Recuperado
de: http://www.ck12.org/probability/Operations-with-
Sets/asmtpractice/Operations-with-Sets-
Practice/?referrer=concept_details