Análisis léxico: Teoría de los lenguajes
Introducción
¡Hola!
Es un gusto encontrarte nuevamente, espero que estés aprendiendo mucho, sobre todo, que tu ánimo no decaiga y sigas conociendo más acerca de los temas que se te presentan.
En esta sesión aprenderemos sobre la teoría de los lenguajes formales. Veremos sobre antecedentes y la teoría de los lenguajes formales.
Un lenguaje se define como un conjunto de cadenas escritas en un alfabeto dado. Para poder formar ese conjunto de cadenas, se definieron operaciones con cadenas y lenguajes.
Las operaciones con cadenas y lenguajes tienen relación con las expresiones regulares. De hecho, éstas últimas se propusieron para especificar conjuntos regulares y lenguajes formales.
Una de las limitaciones de las expresiones regulares es que no pueden usarse para describir lenguajes no regulares o conjuntos no regulares.
Una vez que conozcas la teoría de los lenguajes comprenderás mejor la teoría que está detrás de las expresiones regulares y su relación con la teoría de los autómatas de estado finito.
Los lenguajes independientes de contexto constituyen la base teórica de la estructura de frases de la mayoría de los lenguajes de programación. De hecho, según la jerarquía de Chomsky, los lenguajes regulares son un subconjunto de los lenguajes independientes de contexto.
El campo de la teoría de los lenguajes formales estudia principalmente aspectos puramente sintácticos de tales lenguajes, es decir, sus patrones estructurales internos. La teoría de los lenguajes formales surgió de la lingüística, como una manera de comprender las regularidades sintácticas de los lenguajes naturales. En ciencias computacionales, los lenguajes formales se utilizan entre otras cosas como base para definir la gramática de los lenguajes de programación.
En conclusión, la teoría de los lenguajes formales es un área importante de lingüística y ciencias computacionales. Por lo que, para el ingeniero en sistemas computacionales es muy importante conocer sobre teoría de los lenguajes formales y en general sobre la teoría de los lenguajes de programación.
Prosigamos con energía. Vamos.
¡Mucho éxito!
Desarrollo del tema
Lenguaje formal:
Un lenguaje formal se define como un conjunto de cadenas escritas en un alfabeto dado.
La sintaxis del lenguaje restringe el conjunto de cadenas a aquéllas que satisfacen ciertas propiedades.
Un alfabeto (o clase de carácter) se define como cualquier conjunto finito de símbolos o caracteres.
Una cadena escrita en un alfabeto dado se define como una secuencia finita de caracteres tomados de ese alfabeto.
La longitud de una cadena s se define como |s|.
La cadena vacía es un caso especial de cadena cuya longitud es cero.
Las operaciones que se pueden efectuar con cadenas son:
- Concatenación
Dos cadenas se pueden concatenar para formar una cadena más larga.
s ε = εs = s
x=“Dog” y=“House” => xy = “DogHouse”
- Exponenciación
Una cadena se puede concatenar con ella misma cualquier número de veces.
si =si-1 s (s0=ε)
Operaciones con Lenguajes:
- Unión
Dos lenguajes se pueden unir para formar lenguajes más grandes.
LUM = {s | s está en L o s está en M}
- Concatenación
Las cadenas de dos lenguajes se pueden concatenar para formar un lenguaje más grande con palabras más largas.
LM = {st | s está en L y t está en M}
- Cerradura de Kleene
Las cadenas de un lenguaje se pueden concatenar de un número infinito de maneras para formar cadenas de muchas longitudes y lenguajes muy grandes.
También se puede definir como la repetición de cero o más cadenas de un lenguaje.
Se representa como L*= unión de Li (i = 0 … infinito) = Union(L0, L1, L2,…)
donde
L0 = {ε},
Li = Li-1 L
Por ejemplo:
L={“if”, “while”}
L2= {“ifif”,”ifwhile”, “whileif”, “whilewhile”}- L* = {ε, “if”, “while”, “ifif”,”ifwhile”, “whileif”, “whilewhile”,…}
- L* = {ε, “if”, “while”, “ifif”,”ifwhile”, “whileif”, “whilewhile”,…}
- Cerradura positiva
Es igual a la cerradura de Kleene excepto que no contiene la cadena nula.
Se define como repetición de una o más cadenas de un lenguaje.
Se representa como L+ = unión de Li (i = 1 … infinito)
Por ejemplo para el lenguaje L={“if”, “while”} tenemos- L+ = {“if”, “while”, “ifif”,”ifwhile”, “whileif”, “whilewhile”,…}
Usando las operaciones con lenguajes es posible especificar muchos lenguajes diferentes o sublenguajes. Por ejemplo, el conjunto de todas las cadenas de letras minúsculas y dígitos que empiezan con una letra se puede obtener por medio de:
L(L D)*. Donde D es el conjunto de dígitos y L es el conjunto de letras minúsculas.
Las operaciones con cadenas y lenguajes tienen relación con las expresiones regulares.
El matemático Stephen C. Kleene formuló en 1956 la segunda parte del teorema de Kleene. Este dice que un lenguaje es racional (es decir, es descrito por una expresión regular) si y sólo si es reconocido por un autómata finito. De hecho, Kleene propuso las expresiones regulares para describir lenguajes formales o conjuntos regulares.
Por lo tanto, las operaciones con cadenas y lenguajes descritos se puede decir que forman conjuntos de cadenas o lenguajes regulares.
La jerarquía de Chomsky define qué tan complejo es un tipo de lenguaje. De acuerdo con ésta, los lenguajes regulares son los lenguajes más simples. Enseguida tenemos que los lenguajes libres de contexto son más complejos que los lenguajes regulares.
Conclusión
- Un lenguaje formal se define como un conjunto de cadenas escritas en un alfabeto dado.
- Un alfabeto (o clase de carácter) se define como cualquier conjunto finito de símbolos o caracteres.
- Una cadena escrita en un alfabeto dado se define como una secuencia finita de caracteres tomados de ese alfabeto.
- Las operaciones que se pueden efectuar con cadenas son:
a) Concatenación
Dados dos cadenas s y t, a concatenación de s y t está dada por:
st
b) Exponenciación
Dada una cadena s, la exponenciación de s está dada por:
si = si-1s
con s0 = ε, la cadena nula.
- Las operaciones que se pueden efectuar con lenguajes son:
a) Unión,
Dados dos lenguajes L y M, la unión de L y M está dada por
LUM = {s | s está en L o s está en M}
b) Concatenación,
Dados dos lenguajes L y M, la concatenación de L y M está dada por
LM = {st | s está en L y t está en M}
c) Cerradura de Kleene y
Dado un lenguaje L, la cerradura de Kleene de L está dada por
L* = Union(L0, L1, L2,…)
d) Cerradura positiva
Dado un lenguaje L, la cerradura positiva de L está dada por
L+ = Union(L1, L2, L3,…)
- Las operaciones con cadenas y lenguajes tienen relación con las expresiones regulares.
- Kleene propuso las expresiones regulares para describir lenguajes formales o conjuntos regulares.
- Las operaciones con cadenas y lenguajes forman conjuntos de cadenas o lenguajes regulares.
- La jerarquía de Chomsky define qué tan complejo es un tipo de lenguaje. De acuerdo con ésta, los lenguajes regulares son los lenguajes más simples.
Hemos llegado al final de nuestra sesión. No me resta más que felicitarte por tu esfuerzo y dedicación. Te invito a leer, estudiar y complementar tu aprendizaje por medio del material incluido en la sesión. Recuerda que siempre tendrás el respaldo de tu asesor. No dudes en consultarlo.
Por último, resuelve la consigna de este tema; te invito a cumplir con este compromiso en tiempo y forma.
Nos leemos en la siguiente sesión.