tarea1

Vista previa del material en texto

ACTIVIDAD INDIVIDUAL UNIDAD 1
Tarea 1 - Fundamentación
	Presentado por:
	
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD ESCUELA DE CIENCIAS BÁSICAS TECNOLOGÍA E INGENIERÍA AUTOMATAS Y LENGUAJES FORMALES
Desarrollo de ejercicios
Punto 1)
historia y evolución de la teoría de autómatas y lenguajes formales
 
Ejercicio 2.
Realizar la presentación con la conceptualización y ejemplos de:
1. Alfabeto:
Un alfabeto es un conjunto finito no vacío cuyos elementos se llaman símbolos. Denotamos un alfabeto arbitrario con la letra Σ.
2. Palabra o Cadena:
Una cadena o palabra sobre un alfabeto Σ es cualquier sucesión (o secuencia) finita de elementos de Σ. Admitimos la existencia de una única cadena que no tiene símbolos, la cual se denomina cadena vacía y se denota con .
3. Lenguaje:
Un lenguaje L sobre un alfabeto Σ es un subconjunto de Σ *, es decir L Σ *. Casos extremos:
· L= Ø, L = Σ*, lenguaje vacío.
· lenguaje de todas las cadenas sobre Σ.
Todo lenguaje L satisface L , y puede ser finito o infinito. Los lenguajes se denotan con letras mayúsculas A, B, ,L, M, N.
4. Lenguaje regular:
Es un tipo de lenguaje formal que satisface las siguientes propiedades:
Los lenguajes más sencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de los lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y * de Kleene un número finito de veces.
Puede ser reconocido por:
· un autómata finito determinista
· un autómata finito no determinista
· un autómata de pila
Es generado por:
· una gramática regular
· una gramática de prefijos
Es descrito por:
· una expresión regular
5. Expresión regular:
En cómputo teórico y teoría de lenguajes formales una expresión regular, o expresión racional,12 también son conocidas como regex o regexp,3 por su contracción de las palabras inglesas regular expresión, 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.
6. Expresión de conjuntos:
· Por Extensión
· Por intensión
Decimos que un conjunto está definido por compresión, si sus elementos se describen a través de propiedades que tienen en común.
Un conjunto está definido por extensión, si se enumeran sus elementos.
Por ejemplo: A = {x / x es un número obtenido al lanzar un dado corriente} es un conjunto definido por comprensión ya que sus elementos “x” se describen a través de una propiedad “es un número obtenido al lanzar un dado corriente”.
Esa expresión se lee: “A es el conjunto formado por todos aquellos números que se obtengan al lanzar un dado”.
 Date cuenta que la frase escrita entre las llaves ({...}) está en singular y, sin embargo, 
 se lee en plural.
Ese conjunto, expresado por extensión, es A = {1,2,3,4,5,6}.
7. Palabra nula o vacía ʎ:
En ciencias de la computación y teoría de lenguajes formales, una cadena vacía o string
vacío (en inglés) 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, puesto que
mientras que con este último no se puede operar, esta cadena acepta todas las operaciones
existentes para las cadenas de caracteres (concatenación, asignación, extracción, etc.).
8. Operación regulares – Unión:
Unión: Si ´ L y M son dos lenguajes, su unión se denota ´ por L ∪ M (e.g., L = {11, 00}, 
M = {0, 1}, LcuoM = {0, 1, 00, 11})
9. Operación regulares – Concatenación:
La concatenación de los lenguajes L y M es el conjunto de cadenas que se puede formar
tomando cualquier cadena de L y concentrándola con cualquier cadena de M. Para designar
la concatenación de lenguajes se emplea el punto o ningún operador en absoluto, aunque el
operador de concatenación frecuentemente se llama “punto”. Por ejemplo, si L= {001,10,111} y M = {ε ,001}, entonces L.M, o simplemente LM, es {001,10,111,001001,10001,111001}. Las
tres primeras cadenas de LM son las cadenas de L concatenadas con ε. Puesto que ε es el
elemento identidad para la concatenación, las cadenas resultantes son las mismas cadenas
de L. Sin embargo, las tres últimas cadenas de LM se forman tomando cada una de las
cadenas de L y concatenándolas con la segunda cadena de M, que es 001.
10.Operación regulares - Estrella de Kleene:
La clausura (o asterisco, o clausura de Kleene) de un lenguaje L se designa mediante L^*y
representa el conjunto de cadenas que se pueden formar tomando cualquier número de
cadenas de L, posiblemente con repeticiones (es decir, la misma cadena se puede seleccionar más de una vez) y concatenando todas ellas. 
Por ejemplo, si L = {0,1}, entonces L^*es igual a todas las cadenas de 0s y 1s. Si L = {0,11}, 
entonces L^ (*) constara de aquellas cadenas de 0s y 1s tales que los 1s aparezcan por parejas, 
como por ejemplo 011,11110 y ε, pero no 01011 ni 101. Mas formalmente, L* es la unión infinita 
∪(i≥0) L^i, donde L^0=(ε), L^1=L y L^i, para i>1 es LL• • •L (la concatenación de i copias de L).
11.Operador:
Los operadores son símbolos que indican como se deben manipular los operandos. Los
operadores junto con los operandos forman una expresión, que es una fórmula que define el
calculo de un valor. Los operandos pueden ser constantes, variables o llamadas a funciones,
siempre que estas devuelvan algún valor.
12.Precedencia de los operadores:
La precedencia indica cual es el orden de ejecución de los operadores cuando existen varios.
“En C++ existen 4 aspectos que indican el orden de ejecución de un programa. “Este orden
viene determinado por cuatro condicionantes:
1. Presencia de paréntesis que obligan a un orden de evaluación especifico.
2. Naturaleza de los operadores involucrados en la expresión (asociatividad).
3. Orden en que están colocados (precedencia)
REFERENCIAS BIBLIOGRÁFICAS
· 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
· Mitkov, Ruslan (2003). The Oxford Handbook of Computational Linguistics (en inglés). Oxford University Press. ISBN 978-0-19-927634-9.
· ↑ Lawson, Mark V. (17 de septiembre de 2003). Finite Automata (en inglés). CRC Press. ISBN 978-1-58488-255-8.
· Armas Gómez, S. M. (2011). formas de definir un conjunto. http://recursostic.educacion.es/. http://recursostic.educacion.es/descartes/web/materiales_didacticos/conjuntos_y_opera ciones_agsm/conjuntos_12.html#:%7E:text=formas%20de%20definir%20un
%20conjunto&text=Decimos%20que%20un%20conjunto%20est%C3%A1,si%20se
%20enumeran%20sus%20elementos.&text=Ese%20conjunto%2C%20expresado
%20por%20extensi%C3%B3n,4%2C5%2C6%7D.
· De Castro Korgi, R. (2004). Teoria de la computacion : lenguajes, automatas, gramaticas (Primera edicición ed., Vol. 1). UNIBIBLOS. http://ciencias.bogota.unal.edu.co/fileadmin/Facultad_de_Ciencias/Publicaciones/Archiv os_Libros/Libros_Matematicas/_Teoria_de_la_Computacion	lenguajes	automatas_
 _gramaticas._/teoriacomputacion.pdf