Conceptos Unidad 1 Lenguajes Automatas Introducción a la Teoría de Lenguajes Formales

Conceptos Unidad 1 Lenguajes Autómatas
1 Introducción a la
Teoría de Lenguajes
Formales.
1.1 Alfabeto.
1.2 Cadenas.
1.3 Lenguajes
1.4 Tipos de lenguajes
1.5 Herramientas computacionales ligadas
con lenguajes
1.6 Estructura de un traductor
1.7 Fases de un compilador

1. 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.

2. Longitud de cadena.
La longitud de cadena es el numero 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

3. 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 alfabeto 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

4. 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.
1.2 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.

5. 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.
1.5 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.

6. 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.