tarea1

Vista previa del material en texto

ACTIVIDAD INDIVIDUAL UNIDAD 1 
Tarea 1 - Fundamentacion
Presentado por:
Richard Duque Salgado
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD ESCUELA DE 
CIENCIAS BASICAS TECNOLOGIA EINGENIERIA AUTOMATAS Y LENGUAJES
FORMALES
Desarrollo de ejercicios
Punto 1)
historia y evolucion de la teoria de automatas y lenguajes
formales
Ejercicio 2.
Realizar la presentation con la conceptualization y
ejemplos de:
1. Alfabeto:
Un alfabeto es un conjunto finito no vacfo cuyos elementos se llaman sfmbolos. Denotamos 
un alfabeto arbitrario con la letra I.
2. Palabra o Cadena:
Una cadena o palabra sobre un alfabeto I es cualquier sucesion (o secuencia) finita de 
elementos de I. Admitimos la existencia de una unica cadena que no tiene sfmbolos, la cual 
se denomina cadena vacfa y se denota con X.
3. Lenguaje:
Un lenguaje L sobre un alfabeto I es un subconjunto de I *, es decir L - I *
Casos extremos:
• L= 0, L = I*, lenguaje vacfo.
• lenguaje de todas las cadenas sobre I.
Todo lenguaje L satisface L 0 — ^ ^ , y puede ser finito o infinito. Los lenguajes se
denotan con letras mayusculas A, B, ,L, M, N.
4. Lenguaje regular:
Es un tipo de lenguaje formal que satisface las siguientes propiedades:
Los lenguajes mas sencillos que se consideraran son los lenguajes regulares, es decir, los 
que se pueden generar a partir de los lenguajes basicos, con la aplicacion de las operaciones 
de union, concatenation y * de Kleene un numero finito de veces.
Puede ser reconocido por:
• un automata finito determinista
• un automata finito no determinista
• un automata de pila
Es generado por:
• una gramatica regular
• una gramatica de prefijos
Es descrito por:
• una expresion regular
5. Expresion regular:
En computo teorico y teorfa de lenguajes formales una expresion regular, o expresion 
racional,12 tambien son conocidas como regex o regexp,3 por su contraction de las palabras 
inglesas regular expresion, es una secuencia de caracteres que conforma un patron de 
busqueda. Se utilizan principalmente para la busqueda de patrones de cadenas de caracteres 
u operaciones de sustituciones.
https://es.wikipedia.org/wiki/Lenguaje_formal
https://es.wikipedia.org/wiki/Aut%C3%B3mata_finito%23Aut%C3%B3matas_finitos_deterministas
https://es.wikipedia.org/wiki/Aut%C3%B3mata_finito%23Aut%C3%B3matas_finitos_no_deterministas
https://es.wikipedia.org/wiki/Aut%C3%B3mata_con_pila%23Aut%C3%B3matas_con_pila
https://es.wikipedia.org/wiki/Ciencia_computacional_te%C3%B3rica
https://es.wikipedia.org/wiki/Lenguaje_formal
https://es.wikipedia.org/wiki/Expresi%C3%B3n_regular%23cite_note-Mitkov2003-1
https://es.wikipedia.org/wiki/Expresi%C3%B3n_regular%23cite_note-Regex_info%2C_2017-3
https://es.wikipedia.org/wiki/Car%C3%A1cter_(tipo_de_dato)
https://es.wikipedia.org/wiki/B%C3%BAsqueda_de_patrones
6. Expresion de conjuntos:
• Por Extension
• Por intension
Decimos que un conjunto esta definido por compresion, si sus elementos se describen a 
traves de propiedades que tienen en comun.
Un conjunto esta definido por extension, si se enumeran sus elementos.
Por ejemplo: A = {x / x es un numero obtenido al lanzar un dado corriente} es un conjunto 
definido por comprension ya que sus elementos "x” se describen a traves de una propiedad 
"es un numero obtenido al lanzar un dado corriente”.
Esa expresion se lee: "A es el conjunto formado por todos aquellos numeros que se obtengan 
al lanzar un dado”.
Date cuenta que la frase escrita entre las llaves ({...}) esta en singular y, sin embargo, se lee 
en plural.
Ese conjunto, expresado por extension, es A = {1,2,3,4,5,6}.
7. Palabra nula o vacfa A:
En ciencias de la computacion y teorfa de lenguajes formales, una cadena vacfa o string 
vacfo (en ingles) es la unica cadena de caracteres de tamano cero. Se denota usualmente 
con las letras griegas A o e.
Hacer referencia a una cadena vacfa es distinto a hacer referencia a un Null, puesto que 
mientras que con este ultimo no se puede operar, esta cadena acepta todas las operaciones 
existentes para las cadenas de caracteres (concatenacion, asignacion, extraccion, etc.).
8. Operacion regulares - Union:
Union: Si ' L y M son dos lenguajes, su union se denota ' por L u M (e.g., L = {11,00},
M = {0, 1}, LcuoM = {0, 1, 00, 11})
9. Operacion regulares - Concatenacion:
La concatenacion de los lenguajes L y M es el conjunto de cadenas que se puede formar
tomando cualquier cadena de L y concentrandola con cualquier cadena de M. Para designar
la concatenacion de lenguajes se emplea el punto o ningun operador en absoluto, aunque el
operador de concatenacion 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 concatenacion, las cadenas resultantes son las mismas cadenas
de L. Sin embargo, las tres ultimas cadenas de LM se forman tomando cada una de las
cadenas de L y concatenandolas con la segunda cadena de M, que es 001.
lO.Operacion regulares - Estrella de Kleene:
La clausura (o asterisco, o clausura de Kleene) de un lenguaje L se designa mediante LA*y
representa el conjunto de cadenas que se pueden formar tomando cualquier numero de
cadenas de L, posiblemente con repeticiones (es decir, la misma cadena se puede seleccionar mas 
de una vez) y concatenando todas ellas.
Por ejemplo, si L = {0,1}, entonces LA*es igual a todas las cadenas de 0s y 1s. Si L = {0,11}, 
entonces LA (*) 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 union infinita 
u(i>0) LAi, donde LA0=(s), LA1=L y LAi, para i>1 es LL* • *L (la concatenacion de i copias de L).
ll.Operador:
Los operadores son sfmbolos que indican como se deben manipular los operandos. Los operadores 
junto con los operandos forman una expresion, que es una formula que define el calculo de un 
valor. Los operandos pueden ser constantes, variables o llamadas a funciones, siempre que estas 
devuelvan algun valor.
12.Precedencia de los operadores:
La precedencia indica cual es el orden de ejecucion de los operadores cuando existen varios.
"En C++ existen 4 aspectos que indican el orden de ejecucion de un programa. "Este orden viene 
determinado por cuatro condicionantes:
1. Presencia de parentesis que obligan a un orden de evaluacion especifico.
2. Naturaleza de los operadores involucrados en la expresion (asociatividad).
3. Orden en que estan colocados (precedencia)
REFERENCIAS BIBLIOGRAFICAS
• Hernandez, R. (2010). Practique la teoria de automatas y 
lenguajes formales. (pp. 1 -124). Recuperado de:
http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.ac
tion? docID=10566114&ppg=10
• Mitkov, Ruslan (2003). The Oxford Handbook of 
Computational Linguistics (en ingles). Oxford University 
Press. ISBN 978-0-19-927634-9.
• | Lawson, Mark V. (17 de septiembre de 2003). Finite 
Automata (en ingles). CRC Press. ISBN 978-1-58488-255-8.
• Armas Gomez, 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
%20coniunto&text=Decimos%20que%20un%20coniunto%20
est%C3%A1 ,si%20se
%20enumeran%20sus%20elementos.&text=Ese%20coniunt
o%2C%20expresado
%20por%20extensi%C3%B3n,4%2C5%2C6%7D. •
• De Castro Korgi, R. (2004). Teoria de la computacion : lenguajes, automatas, 
gramaticas (Primera edicicion 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
http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action
http://recursostic.educacion.es/http://recursostic.educacion.es/
http://recursostic.educacion.es/descartes/web/materiales_didacticos/conjuntos_y_operaciones_agsm/conjuntos_12.html%23%3A~%3Atext%3Dformas%20de%20definir%20un%20conjunto%26text%3DDecimos%20que%20un%20conjunto%20est%C3%A1%2Csi%20se%20enumeran%20sus%20elementos.%26text%3DEse%20conjunto%2C%20expresado%20por%20extensi%C3%B3n%2C4%2C5%2C6%7D
http://recursostic.educacion.es/descartes/web/materiales_didacticos/conjuntos_y_operaciones_agsm/conjuntos_12.html%23%3A~%3Atext%3Dformas%20de%20definir%20un%20conjunto%26text%3DDecimos%20que%20un%20conjunto%20est%C3%A1%2Csi%20se%20enumeran%20sus%20elementos.%26text%3DEse%20conjunto%2C%20expresado%20por%20extensi%C3%B3n%2C4%2C5%2C6%7D
http://recursostic.educacion.es/descartes/web/materiales_didacticos/conjuntos_y_operaciones_agsm/conjuntos_12.html%23%3A~%3Atext%3Dformas%20de%20definir%20un%20conjunto%26text%3DDecimos%20que%20un%20conjunto%20est%C3%A1%2Csi%20se%20enumeran%20sus%20elementos.%26text%3DEse%20conjunto%2C%20expresado%20por%20extensi%C3%B3n%2C4%2C5%2C6%7D
http://recursostic.educacion.es/descartes/web/materiales_didacticos/conjuntos_y_operaciones_agsm/conjuntos_12.html%23%3A~%3Atext%3Dformas%20de%20definir%20un%20conjunto%26text%3DDecimos%20que%20un%20conjunto%20est%C3%A1%2Csi%20se%20enumeran%20sus%20elementos.%26text%3DEse%20conjunto%2C%20expresado%20por%20extensi%C3%B3n%2C4%2C5%2C6%7D
http://recursostic.educacion.es/descartes/web/materiales_didacticos/conjuntos_y_operaciones_agsm/conjuntos_12.html%23%3A~%3Atext%3Dformas%20de%20definir%20un%20conjunto%26text%3DDecimos%20que%20un%20conjunto%20est%C3%A1%2Csi%20se%20enumeran%20sus%20elementos.%26text%3DEse%20conjunto%2C%20expresado%20por%20extensi%C3%B3n%2C4%2C5%2C6%7D
http://recursostic.educacion.es/descartes/web/materiales_didacticos/conjuntos_y_operaciones_agsm/conjuntos_12.html%23%3A~%3Atext%3Dformas%20de%20definir%20un%20conjunto%26text%3DDecimos%20que%20un%20conjunto%20est%C3%A1%2Csi%20se%20enumeran%20sus%20elementos.%26text%3DEse%20conjunto%2C%20expresado%20por%20extensi%C3%B3n%2C4%2C5%2C6%7D
http://ciencias.bogota.unal.edu.co/fileadmin/Facultad_de_Ciencias/Publicaciones/Archivos_Libros/Libros_Matematicas/_Teoria_de_la_Computacion___lenguajes__automatas__gramaticas._/teoriacomputacion.pdf
http://ciencias.bogota.unal.edu.co/fileadmin/Facultad_de_Ciencias/Publicaciones/Archivos_Libros/Libros_Matematicas/_Teoria_de_la_Computacion___lenguajes__automatas__gramaticas._/teoriacomputacion.pdf
http://ciencias.bogota.unal.edu.co/fileadmin/Facultad_de_Ciencias/Publicaciones/Archivos_Libros/Libros_Matematicas/_Teoria_de_la_Computacion___lenguajes__automatas__gramaticas._/teoriacomputacion.pdf
http://ciencias.bogota.unal.edu.co/fileadmin/Facultad_de_Ciencias/Publicaciones/Archivos_Libros/Libros_Matematicas/_Teoria_de_la_Computacion___lenguajes__automatas__gramaticas._/teoriacomputacion.pdf