Introducción:
El objetivo de esta unidad es identificar
los conceptos teóricos y necesarios sobre la materia teoría de Lenguajes y
autómatas 1.
Unidad 1 - Introducción
a la Teoría de Lenguajes Formales.
1.1 Alfabeto
Un alfabeto es un conjunto finito no vacío cuyos elementos se llaman
símbolos. Denotamos un alfabeto arbitrario con la letra Σ.
Símbolos:
Es una entidad abstracta que no se puede definir, ya que se dejaría como
una axioma. Igual que se define un punto en la geometría. La cual normalmente
los símbolos son letras (a, b, c,…. z), dígitos (0,1,…9, caracteres (+, -, *,
/,>,< …..). los símbolos pueden estar formados por varias letras o
caracteres.
Alfabeto:
El alfabeto o abecedario es un conjunto de letras, con un determinado
orden. podríamos precisamente decir que el alfabeto es un conjunto de letras
(caracteres o grafemas) de un sistema de escritura, cada una representa
aproximadamente un fonema (consonante o vocal).
1.2 Cadenas.
Una cadena o palabra sobre un alfabeto Σ.
admitimos la existencia de una única cadena que no tiene símbolos, la cual se
denomina cadena vacía y se denota con λ. la cadena vacía desempeña, en la
teoría de lenguajes formales, un papel similar al que desempeña el conjunto
vacío Ø en la teoría de conjuntos.
Longitud de cadena.
La longitud de cadena es el número de símbolos que contiene. La notación
empleada es la que es la que se indica en el ejemplo:
Utilizamos las cadenas de los ejemplos:
I abcb I = 4,
I a + 2*b I = 5
I 000111 I = 6
I if a > b then a = b; I = 9
Cadena Vacía.
Una cadena vacía es la única cadena de caracteres de tamaño cero. Y la
podemos denotar usualmente con letras λ o Є (Griegas).
Concatenación de cadenas.
La concatenación de dos cadenas u y v, escrita uv, es "pegar" las
dos cadenas para formar una nueva.
Ejemplo:
Sea u = ab
v = ca
w = bb. Entonces
uv = abca
uw = cabb
(uv) w = abcabb
u(vw) = abcabb
El resultado de la concatenación de u, v y
w es independiente del orden en que las operaciones son ejecutadas.
Matemáticamente esta propiedad es conocida como asociatividad.
Universo del discurso.
Es un conjunto de todas las cadenas donde
podemos formar con símbolos del alfabeto V le denominamos universo del discurso
de V y la representamos de la siguiente manera W (V). Es evidente que W(V) es
un conjunto infinito y que la cadena vacía pertenece a W(V).
Ejemplo:
Un afabeto con una sola letra V = { a },
podemos decir que el universo del discurso es: W(V) = { λ, a, aa, aaa,
aaaa,....} y asi contiene una cadenas infinitas.
1.1 Lenguajes.
Es un conjunto de cadenas, de todas las
seleccionadas de un Σ*. donde Σ determinado el alfabeto se denomina
lenguaje. Si Σ es un alfabeto y L Σ*, entonces L es un lenguaje de Σ. Observe
que un lenguaje de Σ no necesita incluir cadenas con todos los
símbolos de Σ, ya que una vez que hemos esta que L es un lenguaje de Σ,
también sabemos que es un lenguaje de cualquier alfabeto que sea un súper
conjunto de Σ.
La elección del termino
"lenguaje" puede parecer extraña. Sin embargo, los lenguajes
habituales pueden interpretarse como conjuntos de cadenas. Un ejemplo seria el
Ingles, donde la colección de las palabras correctas inglesas es un conjunto de
cadenas del alfabeto que consta de todas las letras. Otro ejemplo es el
lenguaje C.
Tipos de lenguajes.
Lenguaje natural (castellano)
Nosotros estamos relacionados con el
concepto tradicional de gramática que, de esta forma intuitiva, podemos
considerar un conjunto de reglas el cual nos indican que es correcto y que no
lo es del, lenguaje natural. Con este fin podemos acércanos a la definición mas
clara y formal de la lengua castellana.
Lenguaje artificial.
en este lenguaje aplicamos el mismo método
en el cual definimos un fragmento del lenguaje de programación. Donde
pretendemos describir las instrucciones el cual nos permite asignar un valor a
una expresión ó a una variable en un lenguaje C.
Lenguaje regular.
Llamamos así a los lenguajes porque
sus palabras contienen "regularidades" o repeticiones de los mismos
componentes, por ejemplo en este lenguaje L1 = { ab, abab, ababab,
abababab,...} Este ejemplo podemos apreciar las palabras de L1 son solo
repeticiones de "ab" donde se repiten varias veces. Su regularidad
consiste en las palabras que contienen "ab" varias veces.
Herramientas computadoras ligadas con lenguajes.
Traductor.
Un traductor es un programa que tiene como
entrada un texto escrito en un lenguaje (lenguaje fuente) y como salida produce
un texto escrito en un lenguaje (lenguaje objeto) que preserva el significado
de origen.
Ejemplos de traductores son los
ensambladores y los compiladores.
Compilador.
El compilador es un programa informático
que traduce un programa escrito en lenguaje de programación y lo pasa a
lenguaje de programación, podemos decir que este programa nos permite traducir
un código fuente de un programa en lenguaje de nivel alto, y lo pasmos a otro
nivel inferior (lenguaje maquina).
Ensambladores.
El ensamblador es el programa en que se
realiza la tracción de un programa escrito en ensamblador y lo pasa a lenguaje
maquina. Directa o no directa la traducción en que las instrucciones no son mas
que instrucciones que ejecuta la computadora.
Interpretes.
Los interpretes son los que realizan
normalmente dos operaciones:
- Traducen
el código fuente a un formato interno.
- Ejecuta
o interpretan el programa traducido al formato interno.
Donde la primera pertenece al interprete
el cual llama a veces al compilador, así se genera el código interno, pero no
es el lenguaje de maquina, ni lenguaje de símbolos, ni mucho menos un lenguaje
de nivel alto.
Conclusión
De esta manera se vio los conceptos
teóricos de alfabeto, cadena, símbolo, longitud de cadena, etc. Así como cada
uno de sus temas y subtemas.
