Tarea 1. Fundamentación: Estudiante: José Mauricio Saavedra

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 21

Tarea 1.

Fundamentación

Estudiante: José Mauricio Saavedra

Universidad Nacional Abierta y a Distancia


Vicerrectoría Académica y de Investigación
Escuela de Ciencias Básicas, Tecnología e Ingeniería
Ingeniería en Sistemas
Autómatas y lenguajes formales
Agosto 2021
1. Consulta de material en
bases de datos
Science direct: Títulos encontrados

Base de Bibliografía sintesis


datos
Habla del paquete JFLAP, el cual es una
Alecha, M., & Hermo, M. (2009). A learning algorithm for deterministic
herramienta gratuita e interactiva de visualización y
finite automata using JFLAP. Electronic Notes in Theoretical Computer
enseñanza para idiomas formales. Se implementa el
Science, 248, 47-56. Recuperado de:
algoritmo de Dana Angluin que puede aprender
https://www.sciencedirect.com/science/article/pii/S1571066109002813
Autómatas Deterministas finitos (material en inglés)

González Miranda, O., & Cerrada Lozada, M. (2014). Diagnóstico de Habla de la necesitad de diagnosticadores más
Sistemas de Eventos Discretos Controlados: Un Enfoque Basado en sencillos y eficientes debido a la complejidad de los
Science Crónicas y Análisis Modular Usando Modelos de Autómatas. Revista procesos industriales. El diagnóstico modular ha
Iberoamericana de Automática e Informática industrial, 11(2), 191-201. mostrado ser eficiente en la reducción de la
direct Recuperado de complejidad asociada a los sistemas de eventos
https://www.sciencedirect.com/science/article/pii/S1697791214000090 discretos.

Mora-Lopez, L., Mora, J., Morales-Bueno, R., & Sidrach-de-Cardona, M.


En este articulo se propone un modelo para
(2005). Modeling time series of climatic parameters with probabilistic
caracterizar y predecir series de tiempo continuas a
finite automata. Environmental Modelling & Software, 20(6), 753-760.
partir de técnicas de aprendizaje automático.
Recuperado de:
(material en inglés)
https://www.sciencedirect.com/science/article/pii/S1364815204001112
ebsco: Títulos encontrados

Base de Bibliografía: Articulo científico – APA 6.0 sintesis


datos
Su contenido abarca los temas de máquinas, lenguajes y
problemas, Máquinas de Turing - Autómatas finitos,
Alfonseca Cubero, E., Morrión Salomón, R., & Alfonseca Moreno,
Autómatas a pila, Gramáticas y máquina. Lenguajes
M. (2000). Teoria de autómatas y lenguajes formales. McGraw-Hill
regulares, Lenguajes independientes del contexto,
Interamericana.
Computabilidad y complejidad y otras máquinas y
gramáticas.

Se abordan los conceptos básicos, lenguajes regulares y


Mercado Polo, D., & Hoz Franco, E. de la. (2009). Lenguajes
expresiones regulares. Diagramas de transición y
ebsco formales y teoría de autómatas finitos. fundamentos para la creación
autómatas finitos, Lenguajes y tipos de gramáticas.
de un traductor (1 ed). Educosta.
Autómatas con pila y Máquinas de Turing

Este material brinda los conocimientos fundamentales


Cases Muñoz, R. (2002). Lenguajes, gramáticas y autómatas. curso
para que adquiera las habilidades y técnicas para construir
básico. Alfaomega Grupo Editor.
gramáticas generadoras de lenguajes
dialnet: Títulos encontrados

Base de datos Bibliografía: Articulo científico – APA 6.0 sintesis

En este libro se manejan y explican los conceptos básicos


Kelley, D., & Platas, M. L. D. (1995). Teoría de autómatas y de la teoría de autómatas, lenguajes regulares y
lenguajes formales (Vol. 22). Prentice Hall. Recuperado de: expresiones regulares. Diagramas de transición y
https://dialnet.unirioja.es/servlet/libro?codigo=326783 autómatas finitos, Lenguajes y tipos de gramáticas.
Autómatas con pila

dialnet

Formella, A. (2010). Teoría de autómatas y lenguajes Este material brinda los conocimientos fundamentales
formales. Departamento de Informática, Universidad de de para que adquiera las habilidades y técnicas para construir
Vigo, Junio.qui gramáticas generadoras de lenguajes.
Ejercicio 2. presentación
de conceptualización de
términos y ejemplos
conceptos

01 02 03

alfabeto palabra lenguaje


Es un conjunto finito no vacío, cuyos Secuencia finita de símbolos de un
elementos se denominan letras o Es un conjunto de cadenas, todas
alfabeto.
símbolos. Denotamos ellas seleccionadas de un alfabeto.
un alfabeto arbitrario con la letra Σ. Los lenguajes habituales pueden
Ejemplo:
interpretarse como conjuntos de
Teniendo el alfabeto Σ={ 0, 1 , 3 } ,
Ejemplo: Σ={ 0, 1 , 3 } cadenas.
una palabra puede ser 01 , 11, 00 o
Ejemplo: El inglés ya que la colección
todas las combinaciones posibles de
de las palabras correctas inglesas es
los elementos de ese alfabeto
un conjunto de cadenas del alfabeto
Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales que consta de todas las letras
4. Lenguaje regular
Un lenguaje regular es un tipo de lenguaje
formal que se puede generar a partir de los
lenguajes básicos, con la aplicación de las
operaciones de unión, concatenación y estrella
de Kleene un número finito de veces.

Todo lenguaje formal finito constituye


un lenguaje regular

Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales


5. Expresión regular
Son las unidades de descripción de los lenguajes regulares, que
se incluyen en los denominados lenguajes formales. Es una
secuencia de caracteres que conforma un patrón de búsqueda.
Se utilizan principalmente para la búsqueda de patrones de
cadenas de caracteres u operaciones de sustituciones.

Expresión Descripción

[a-zA-Z0-9]+ Uno o más caracteres


alfanuméricos

[0-5] Un número de 0 a 5

[a-z] {3} Exactamente tres letras


minúsculas

Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales


6.Expresión de conjuntos

Por extensión Por intención


Un conjunto por extensión como Conjunto cuyos elementos se
aquellos conjuntos cuya notación describen a través de
indica cada uno de los propiedades que tienen en
elementos que los componen. común.

Ejemplo: Conjunto de números pares Ejemplo:


menores que 10 A = {x / x es un número
obtenido al lanzar un dado
C={ 2 , 4 , 6, 8} corriente}
Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales
7.Palabra nula o vacía ʎ
En ciencias de la computación y teoría
de lenguajes formales, una cadena vacía es
la única cadena de
caracteres de tamaño cero. Se denota
usualmente con las letras griegas λ o ϵ.

Hacer referencia a una cadena vacía es


distinto a hacer referencia a un Null.

Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales


Operaciones
regulares
8. Unión
La unión de dos lenguajes regulares es
otro lenguaje regular. Se utiliza la
operación de unión de conjuntos; así, para
el alfabeto S ={x,y} si L1 = {x,xy} y L2 =
{yz,yy} entonces su unión será L1 È L2 =
{x,xy,yz,yy }.

Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales


9. concatenación
La concatenación de dos lenguajes
regulares es otro lenguaje regular. Se
concatenan una cadena del primer
lenguaje y una cadena del segundo.
Con L1 y L2 anteriores la
concatenación (que se denota °) será
L1 ° L2 ={xyx,xyy,xyyz,xyyy}. La
concatenación no es conmutativa
(L1 ° L2 ¹ L2 ° L1 ).

Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales


10. Estrella de kleene
Es una operación unaria que se aplica sobre
un conjunto de cadenas de caracteres o un
conjunto de símbolos o caracteres (alfabeto), y
representa el conjunto de las cadenas que se
pueden formar tomando cualquier número de
cadenas del conjunto inicial, posiblemente con
repeticiones, y concatenándolas entre sí.

Ejemplo de clausura de Kleene aplicada a un


carácter:
{a}*={λ , a , aa , aaa , aaaa}

Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales


11. operador
Son los simbolos que exprezan
las operaciones a realizar entre
los conjuntos de lenguajes
operadores
+ Yuxtaposición
Representa la Símbolo de no operador,
unión. L(E + F) = como en xy que significa
L(E) ∪ L(F) x × y) para representar la
concatenación. L(EF) =
L(E)L(F)

Representa la cerradura.
* () Parentesis
L(E∗ ) = (L(E))∗ , donde L Si “E” es una expresión
∗ = {ǫ} ∪ L ∪ LL ∪ LLL ∪ regular, entonces (E), E entre
paréntesis, también es una
expresión regular que denota
el mismo lenguaje que E
Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales
12
Precedencia de los operadores
Precedencia de operadores
1. El asterisco de la cerradura tiene la mayor precedencia. Aplica sólo a la secuencia de
símbolos a su izquierda que es una expresión regular bien formada.
2. Concatenación sigue en precedencia a la cerradura, el operador “dot”.
3. Después de agrupar los asteriscos a sus operandos, se agrupan los operadores de
concatenación a sus operandos

4. Se agrupan todas las expresiones yuxtapuestas (adyacentes sin operador interviniendo)


5. Concatenación es asociativa y se sugiere agrupar desde la izquierda (012 se agrupa
(01)2).
6. La unión (operador +) tiene la siguiente precedencia, también es asociativa.
7. Los paréntesis pueden ser utilizados para alterar el agrupamiento
EJEMPLOS

• L(001) = 001.
• L(0 + 10∗ ) = {0, 1, 10, 100, 1000, . . .}.
REFERENCIAS BIBLIOGRAFICAS
1. Carrasco, R. C., Calera Rubio, J., & Forcada Zubizarreta, M. L. (2000). Teoría de lenguajes, gramáticas y
autómatas para informáticos. Digitalia. (pp. 127 - 142). Recuperado
de https://bibliotecavirtual.unad.edu.co/login?url=https://search-ebscohost-
com.bibliotecavirtual.unad.edu.co/login.aspx?direct=true&db=nlebk&AN=318032&lang=es&site=ehost-
live&ebv=EB&ppid=pp_Cover
2. Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales. Universidad de Extremadura. Servicio de
Publicaciones. (pp. 39 - 70). Recuperado
de https://bibliotecavirtual.unad.edu.co/login?url=http://search.ebscohost.com/login.aspx?direct=true&db=edsbas&
AN=edsbas.62161440&lang=es&site=eds-live&scope=site
3. González, A. [Ángela]. (2017, noviembre 5). Autómatas Finitos. [Archivo de video]. Recuperado
de http://hdl.handle.net/10596/10470
4. González, A. [Ángela]. (2018, junio 1). Lenguajes Regulares. [Archivo web]. Recuperado
de http://hdl.handle.net/10596/18315

También podría gustarte