Upload
miguel-angel-garces-sanchez
View
213
Download
0
Embed Size (px)
Citation preview
7/25/2019 Actividad Colaborativa Para El Momento No 2 Automatasunad
1/5
ACTIVIDAD COLABORATIVA PARA EL MOMENTO No: 2 AUTOMATAS Y LENGUAJES FORMALES
Nombre del Estudiante : MIGUEL ANGEL GARCES SANCHEZ
Codigo : 1057489070
CEAD : VELEZ
Nombre del Tutor : EDUARDO SOLANO
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA
ESCUELA DE CIENCIAS BASICAS , TECNOLOGIA E INGENIERIA
INGENIERIA DE SISTEMAS
2016
7/25/2019 Actividad Colaborativa Para El Momento No 2 Automatasunad
2/5
PARTE 1
PUNTO 1
M es quntuplo determinado as:{ , , , ,}[
K se refiere al conjunto de los estados de nuestro autmata:
K ={ 0 ,, 3 , , }
refiere al lenguaje :
= {a , b}
S es el estado inicial:
S = 0
es la funcin de transicin del autmata podemos denotar asi :
K x k ( Quiere decir que si tenemos un estado , un lenguaje , mas transicin = nos puede
resultar un nuevo estado y as vamos organizando )
(q0,a)= q0 (q0,a)= q0 (q1,a)= q4 (q1,a)= q1 (q2,b)= q3 (q2,b)= q2 (q3,b)= q2 (q3,a)= q3 (q4,a)= q6 (q4,b)= q4 (q5,a)= q7 (q5,b)= q5
M= ({q0,q1, q2, q3, q4, q5}, {a,b}, , {q0}, {q1, q2, q4})
7/25/2019 Actividad Colaborativa Para El Momento No 2 Automatasunad
3/5
a b
0
Q0
q1 Q1 Q1
q2 Q2 Q2
q3 Q3 Q3
q4 Q4 Q4
q5 Q5
= { { }| = + + () + () + (() + 1(() + ()))}
= (0, 3) = ()
= (0, ) = ()
3 = (0, ) , = ()()
= (0, 4) , 3 = ()
= (0, 5) , , 3 = ()()
ER= + + 3 + + Por lo tanto ser:
() + () + ()() + ()()
4. Identifique los estados Distinguibles y los No distinguibles
Minimizacin del Autmata utilizando el mtodo de conjuntos:
Conjuntos Inciales:
X Estados finales
Q3 , Q4 ,Q5
7/25/2019 Actividad Colaborativa Para El Momento No 2 Automatasunad
4/5
y , 1 , 2 Estados no finales
= {0, 1}
5. En el proceso de eliminacin de estados, identifique que transiciones seeliminan y cules se re direccionan. Muestre la tabla de estados
distinguiblesSe crea nuevamente una tabla de transicin del autmata final minimizado
K A B
y w z
#x w z
z n x
w x n
n z w
6. .
Las gramticas son mecanismos generadores de lenguajes, es decir nos indican
cmo podemos obtener o construir palabras de un determinado lenguaje.
Una gramtica independiente del contexto (GIC) es una cudrupla G=(N, , S, P),
donde:
N: es una coleccin finita (no vaca) de smbolos no terminales.
: es un alfabeto.
S: es un no terminal llamado smbolo inicial.
P: un conjunto de producciones tal que PN (N)*.
Los lenguajes generados por una GIC son llamados Lenguajes Independientes
del Contexto (LIC). Es posible probar que la gramtica independiente del contexto
dada por: S aSb|
7/25/2019 Actividad Colaborativa Para El Momento No 2 Automatasunad
5/5
Para verificar que tipo de gramtica es en el simulador JFLAP nos dirigimos a la
ventana que se exporta despus de haber convertido el DFA a Gramtica (ver
ms adelante) y en el men Test seleccionamos prueba de tipo de gramtica
(Test For Grammar Type).
Par ver qu tipo de gramtica es en el simulador (JFLAP) nos ubicamos en elmen convert y elegimos la opcin Convert to Grammar; esto si el autmata
finito es determinista de lo contrario debemos convertirlo primero en un autmata
finito Determinista y luego realizar el proceso para convertir a la gramtica, en este
caso estamos trabajando con un autmata finito determinstico as que no es
necesario.
BIBLIOGRAFA
http://www.veoh.com/watch/v616083236Thn5HJn
https://www.youtube.com/watch?v=eWUfPJD9A_0&feature=youtu.be
https://www.youtube.com/watch?v=3kWdHOLw-AQ
https://www.youtube.com/watch?v=ASg_ZUXgvZk
https://www.youtube.com/watch?v=sW-Lx9p1xfc
https://www.youtube.com/watch?v=I4wI0mwQYow
https://www.youtube.com/watch?v=-mZ