UNIVERSIDAD
NACIONAL ABIERTA Y A DISTANCIA
Escuela de ciencias básicas tecnologías e Ingeniería
301405- AUTOMATAS Y LENGUAJES FORMALES
2013- 2 Inter semestral
ACTIVIDAD No. 2
GUIA DE ACTIVIDAD
TRABAJO COLABORATIVO N. 1
LENGUAJES REGULARES
Elaborado por:
Luis Alberto Sanchez C
CC 16.786.134
Grupo # 1
Tutor
Alfonso Alexander López
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA
PALMIRA
Noviembre – 2013
INTRODUCCION
Los lenguajes pueden describirse como elementos
que se generan, como cadenas a partir de cadenas sencillas, con el uso de
operaciones de cadenas o el desarrollo del lenguaje mismo, que se puede generar
con otros lenguajes más sencillos mediante operaciones de conjuntos.
Los Lenguajes más sencillos son los
considerados lenguajes regulares, es decir, los que se pueden generar a partir
de lenguajes de un elemento con la aplicación de ciertas operaciones estándar
realizadas un número finito de veces.
Estos son pues los lenguajes que pueden
reconocer los dispositivos llamados Autómatas finitos (AF) que son máquinas de
cómputo con memoria muy restringida. En esta unidad se considera como segundo
aspecto la idea de que un lenguaje no sea regular, además de proporcionar un
modelo sencillo de computación que se puede generalizar en las unidades
siguientes.
Con las caracterizaciones anteriores y otras de los
lenguajes regulares se obtienen y estudian algoritmos para traducir una
descripción de un lenguaje a otra descripción de un tipo distinto; se acumula
experiencia en el uso de métodos formales para describir lenguajes y se intenta
responder a preguntas acerca de ellos, son preguntas y ejercicios sencillos con
sus respuestas y que permiten determinar la utilidad de los lenguajes regulares
en aplicaciones del mundo real.
OBJETIVO
GENERAL
·
Reconocer
los lenguajes regulares, autómatas finitos y su aplicación.
OBJETIVOS
ESPECIFICOS
·
Estudiar
la aplicación de los lenguajes regulares y los autómatas finitos.
·
Adquirir
las habilidades necesarias para desarrollar autómatas y máquinas que reconozcan
lenguajes o computen funciones.
·
Distinguir
los diferentes tipos de lenguajes formales existentes.
·
Adquirir
el conocimiento y competencia para poder recrear autómatas sencillos en un
simulador. De igual forma verificar el lenguaje que reconoce.
EJERCICIO A DESARROLLAR:
Para el siguiente Autómata Finito denotado como:
A=
(E = {1,2,3}, Q = {q, q , q}, f, q, F = {q } ) donde f
vine dada por la siguiente tabla:
F
|
1
|
2
|
3
|
Q1
|
Q1
|
Q1
|
Q2
|
Q2
|
Q3
|
Q3
|
Q3
|
Q3
|
Q3
|
Q3
|
Q3
|
1. Corrija
la tabla de transición indicando el estado inicial y final.
R/
F
|
1
|
2
|
3
|
►Q1
|
Q1
|
Q1
|
Q2
|
Q2
|
Q3
|
Q3
|
Q3
|
#Q3
|
Q3
|
Q3
|
Q3
|
En la tabla anterior se representa:
§
►Q1 representa el estado inicial,
§
#Q3 representa el estado final.
2. Construya
el diagrama de Moore correspondiente.
3.
Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta.
R/ Partiendo de las definiciones del material
suministrado así: Autómata Finito Determinista (AFD) es aquel autómata finito
cuyo estado inicial y el carácter leído por el autómata. Formalmente, un
autómata finito determinista (AFD) es similar a un autómata de estados finitos,
representado con una 5-tupla.
Autómatas Finitos No Determinísticos (AFN), se puede
obtener a partir de la de AFD. Es decir, tendremos un conjunto finito de
estados L, un alfabeto de entrada I, un estado inicial o de partida s*, un
conjunto de estados aceptados A y una regla de transición. La única diferencia
que existe se encuentra en las reglas de transición. En un AFN, las reglas asocian pares (S, q)
con Cero o más estados. Se puede decir que las reglas relacionan pares (S, q)
con colecciones de conjuntos de estados.
Esto conduce a una diferencia significativa entre un autómata
de estado finito no determinístico y un autómata de estado finito que en éste
último la función de estado siguiente conduce a un estado unívocamente
determinado, mientras que en un AFN la función de estado siguiente lleva a un
conjunto de estados. Finalmente, la definición de AFND es un dispositivo que
tiene un número finito de estados, algunos de los cuales son los estados
iniciales y, por lo menos uno, es un estado de aceptación. Cada estado tiene
que discernir entre un conjunto de caminos válidos, examinando si estos
conducen a un estado de aceptación; nada permite diferenciar entre dos caminos
hechos por el mismo símbolo de entrada.
Por lo tanto tal
como se observan que se no se definen dos o más transiciones, por tal
razón se dice que el Autómata Finito es Determinístico (AFD).
4. Identifique
los elementos (tupla que es). Debe explicar y describir cada elemento y la
función y significado en el autómata. Conceptos
y definiciones adicionales.
R/ Formalmente,
una autómata finito determinista (AFD) es similar a un Autómata de estados
finitos, representados con 5-tupla (K, Σ, q°, δ, F) donde:
·
K un
conjunto de estados = {q1,q2,q3};
·
Σ es una alfabeto = {1,2,3};
·
q° es el estado
Inicial = q1;
·
δ es
la función de transición dada por {q1,q2,q3}*{1,2,3};
δ(q2,1)=q3 δ(q2,2)=q3 δ(q2,3)=q3
δ(q3,1)=q3 δ(q3,2)=q3 δ(q3,3)=q3
·
A es
un conjunto de estado de aceptación o de finales =q3.
Que se representa:
§
M{(1,2,3),(q1,q2,q3)}
§
Q1
Entrada inicial.
§
Q3
Etapa final.
5. Identifique
la ER que lo representa. Explique los operadores y cómo actúan en la función.
R/ Utilizando el software se desarrolla paso a paso la
conversión a expresión regular (ER).
Una expresión regular (ER) es una notación normalizada
para representar lenguajes regulares. Las expresiones regulares permiten
describir con exactitud y sencillez cualquier lenguaje regular. Para definir
una ER se pueden utilizar todos los símbolos del alfabeto Σ y, además λ y ϕ . Los operadores que también se pueden utilizar son:
·
+
representa la unión.
·
.
representa la concatenación
·
representa el cierre de Kleene
·
( )
Modifican las propiedades de los demás operadores.
La ER obtenida corresponde a = (1+2)*3(1+2+3)(1+2+3)*
6. Identifique
el lenguaje que genera.
R/ Con la ayuda del software JFLAP se obtuvo la expresión
regular minimizada. Se debe tener en cuenta que:
·
q+ es una unión,
·
q* representa
muchas veces un proceso
·
((1,2)* 3(1,2,3)(1,2,3)*
·
M= {(0,1,2,3),(q1,q3)}
Tabla de transición:
F
|
0
|
1
|
2
|
3
|
►Q1
|
Q1, 3q3
|
Q1,3q3
|
3q3
|
|
#Q3
|
Q1
|
Q3
|
Q3
|
Q3
|
El lenguaje que reconoce el autómata AFD presenta varias opciones así:
·
Puede
empezar con (1, o 2) el número de veces que quiera repetir, pero para pasar al
estado q2 necesita 3 y después cualquier numero entre (1,2, o 3) para pasar a q3 y por ultimo cualquier numero
entre 1,2, o 3.
La ecuación seria
((1 + 2 )* (3)(1+2+3)(1+2+3)
R/ Decidí utilizar la siguiente cadena valida 1122231122
Inicialmente empieza la secuencia en Q1 donde va estar cíclicamente 1122231122
En este paso se pasa de Q1 a Q2 por que ingresa el 3 - 1122231122
Finalmente se pasa de Q2 a q3 con el 1 y continúa en 1122 hasta finalizar
la cadena valida y parar.
8. Muestre
el diagrama de Moore generado en JFLAP y en VAS y comente que similitudes o
diferencias encuentra al realizarlo en los dos simuladores. (Herramientas que ofrezcan
uno u otro).
R/Inicialmente empecé a utilizar VAS pero encontré
limitaciones en las simulaciones y en las limitaciones de conversiones, después
trate con JFLAP y sin lugar a dudas tiene muchas más herramientas de uso que el
primero.
Ahora si comparamos el diagrama de Moore entre los dos se ve mucho mejor
con Vas pero no permite muchas otras simulaciones.
Ahí presento otro ejemplo con JFLAP me permite correr
varias cadenas de entrada al tiempo y evaluar su grado de aceptabilidad.
Ahí está otro ejemplo
de JFLAP me permitió convertir a gramática
9.
Genere la tabla de transición en VAS y plásmela en el documento, compárela con
la plasmada en el ejercicio.
R/ Ambas tablas de transición tanto del VAS como del
ejercicio no muestran ni el estado inicial como tampoco el estado final de
aceptación, por tal razón la tabla de transición representa una parte de la
información para poder entender claramente un AFD.
10 Por último,
identifique las cadenas válidas que generan las siguientes ER: muestre algunas,
pero más que las cadenas identifique el lenguaje que representa. Seleccione una
ER (solo una) y expórtela o genere el autómata o el diagrama de Moore que sea
válido.
a) 0*+1*(01)
b) 10* + 10
c) 01* + 0
d) (1.11*0) *
e) (1 + 10) +
0
f) 1* 0*10
g) 00* 11*
h)
(0+1)*11(1+0)*
CONCLUSIONES
• Tal como se observa en el documento base de la
catedra lógica matemática se puede comprender que servirá para desarrollar
competencias para expresar razonamientos lógicos en lenguaje simbólico.
• El uso del software JFLAP sin lugar a dudas presenta
muchas herramientas que permite simular y comprender cadenas fácilmente y a la
vez facilita las practica del contenido general del curso.
BIBLIOGRAFIA
•
http://www.cimm.ucr.ac.cr/cuadernos/documentos/Normas_APA.pdf
• Modulo Logica Matematica, Autor Georffrey Acevedo
Gomez, UNAD, Medellin, 2012
No hay comentarios.:
Publicar un comentario