Introducción a la teoría de los lenguajes formales
En este tema, nos vamos a enfocar, en los conceptos de lenguajes formales para comprender las fases de un compilador y traductor.
Comenzaremos por definir algunas partes esenciales para poder entender el tema con mayor facilidad. En este tema los conceptos básicos que veremos serán símbolo, alfabeto, cadena y lenguaje así como las propiedades y operaciones que se pueden hacer con ellos.
Símbolo:
Se refiere a todo aquella representación que puede ser apreciable gracias a la vista como es una letra, número, señal o cualquier otro elemento que tiene significado.
Alfabeto:
Se refiere a un conjunto ordenado de símbolos, el cuál, tiene la característica de ser finito y no vacío.
Operaciones con alfabetos
Sobre los alfabetos, se pueden aplicar una serie de operaciones u propiedades las cuales aplicárselas a estos, los resultados alcanzados, también pueden llamarse o considerarse alfabetos siempre y cuando sean finitos y no vacíos.
Operaciones
Ejemplos:
En los ejercicios anteriores en el caso del ejercicio d, se resuelve cada paréntesis por separado y luego se aplica la diferencia simétrica.
Cadenas:
Consisten en una secuencia finita de símbolos yuxtapuestos (Poner una cosa junto a otra o inmediatamente a otra cosa) pertenecientes todo a un mismo alfabeto.
En la cadena de la siguiente imagen, podemos afirmar que no es una cadena del alfabeto sigma, porque no todos los símbolos pertenecen al alfabeto.
Operaciones y propiedades con cadenas
Logitud |w|
Cantidad de símbolos que tiene la cadena
Concatenación
Es la yuxtaposición o unión de dos o más cadenas
algo importante que decir acerca de la concatenación es que esta no es conmutativa esto significa que:
Inversa de una cadena w’
Se refiere a invertir los valores, es decir, cada símbolo ocupa la posición contraria a la posicion actual
Propiedades de la inversa
Cadena vacía
Es una cadena que no tiene símbolos, la cual se denota por ε
propiedades de la cadena vacía
Potencia de cadenas
Se refiere a la cantidad de veces que voy a concatenar w con ella misma.
De manera más formal podemos decir que:
Sea w una cadena formada a partir de un alfabeto Σ, entonces para cualquier n≥0, se tiene que la enésima potencia de w se puede definir recursivamente como:
Lenguaje:
Consiste en un conjunto de cadenas contruidad a partir de símbolos de un determinado alfabeto, y a diferencia de los alfabetos, los lenguajes si pieden ser infinitos y vacíos.
Operaciones básicas de lenguajes
Al igual que los alfabetos, también en los lenguajes podemos aplicar las operaciones de conjuntos. y el resultado también es considerado lenguaje.
además de las operaciones anteriores, tenemos:
Concatenación
Potencia
Cerradura de estrella o de Kleene
Cerradura positiva
Concatenación Li+Lj
En la concatenación de lenguajes cada cadena en el leguaje Li, deberá de concatenarse con todos y cada uno de las cadenas obtenidas en el lenguaje Lj. Respetando el orden indicado para la concatenación, y al igual que el los alfabetos no es conmutativa.
Potencia del lenguaje
Concatenación sucesiva de un lenguaje consigo mismo tantas veces como lo inique n
De manera más formal podemos decir que:
Sea L un lenguaje formado a partir de un alfabeto Σ, entonces para cualquier n≥0, se tiene que la enésima potencia de L se puede definir recursivamente como:
Cerradura estrella o cerradura de Kleene
Se refiere a la union de todas las potencias de un lenguaje iniciando desde 0 hasta infinito
De manera más formal podemos decir que:
Sea L un lenguaje formado a partir de un alfabeto Σ, se define a L* como cerradura de Kleene o cerradura estrella como la union infinita de todas las potencias de L, incluyendo la potencia 0.
Cerradura positiva
Se refiere a la unión de todas las potencias de un lenguaje iniciando desde la potencia 1 hasta infinito
De manera más formal podemos decir que:
Sea L un lenguaje formado a partir de un alfabeto Σ, se define a L+ como cerradura positiva como la union infinita de todas las potencias de L, a partir de uno.
Propiedades de las cerraduras
Para cualquierr lenguaje se cumplen las siguientes propiedades:
Inversa de un lenguaje:
Se refiere al conjunto de todas las cadenas inversas tal que cada cadena pertenece al lenguaje.
Propiedades del lenguaje inverso
