Introducción a la Teoría de Lenguajes Formales
Autor: José Antonio Diaz
Ejemplos:
Contenido
1.1 Alfabeto
Símbolo: Es una entidad abstracta (indivisible) ya sea letras, dígitos o caracteres. Los símbolos también pueden estar formados por varias letras o caracteres.Ejemplos:
V1= { a, b, c, d, ... z }
V2 = { 0, 1 }
Java = { {, }, for, if, else, while, ... }
Alfabeto: Conjunto no vació cuyos elementos se llaman símbolos, se denomina por ∑.
1.2 Cadenas
Cadena o palabra: Secuencia finita de símbolos de un determinado alfabeto.
Cadena vacía: Denotada por λ. La palabra vacía pertenece a los lenguajes universales de todos los alfabetos posibles.
Longitud de cadena: Es el numero de símbolos que contiene.
| λ | = 1
| aba | = 3
| 010 | = 3
Ejemplo:
Si w = abra y v = cada
Entonces
wvbra = abracadabra
Concatenación: Cuando se escriben varias palabras o caracteres uno a continuación de otro y forman una palabra.
Ejemplo:
Si w = abra y v = cada
Entonces
wvbra = abracadabra
La concatenación de palabras es asociativa, esto es, ( xy ) z = x ( yz ), pero no conmutativa en el caso general. La longitud de una concatenación cumple la propiedad | uv | = |u| + |v|.
(Brena, 2003, pg. 17).
Existe un elemento neutro. La palabra vacía ( λ ) es el elemento neutro de la concatenación de palabras, tanto por la derecha, como por la izquierda. En efecto, sea x una palabra cualquiera. Se cumple que:
λx = xλ = x
(Alfonseca Moreno, M., y otros, 2006, pg. 6).
Potencia: ∑ = { a, b }
w = ab
w0 = λ
w1 = ab
(Alfonseca Moreno, M., y otros, 2006, pg. 6).
Potencia: ∑ = { a, b }
w = ab
w0 = λ
w1 = ab
w2 = abab
w3 = ababab
w4 = abababab
Potencia de un alfabeto: ∑ = { 0, 1 }
∑ 1 = { 0, 1 } ---> Lenguaje donde cada palabra solo tiene 1 símbolo.
∑ 2 = { 00, 01, 10, 11.. }
∑ 3 = { 000, 001, 010, 011... }
∑ 4 = { 0000, 0001, 0111... }
Cada potencia del alfabeto es un lenguaje.
Potencia de un alfabeto: ∑ = { 0, 1 }
∑ 1 = { 0, 1 } ---> Lenguaje donde cada palabra solo tiene 1 símbolo.
∑ 2 = { 00, 01, 10, 11.. }
∑ 3 = { 000, 001, 010, 011... }
∑ 4 = { 0000, 0001, 0111... }
Cada potencia del alfabeto es un lenguaje.
Subcadena: Una palabra v es subcadena de otra w cuando existen x, y.
Ejemplo
w = xvy v es una subcadena de w
Si se tiene la palabra vibora, bora es una subcadena. λ es una subcadena de toda palabra.
(Brena, 2003, pg. 17).
(Brena, 2003, pg. 17).
Universo del discurso (Lenguaje universal): Es el conjunto de todos las cadenas (palabras) que se pueden formar con los símbolos de un alfabeto incluyendo la cadena vacía. Según Alfonseca (2006) "el conjunto de todas las palabras que se pueden formar con las letras de un alfabeto se llama lenguaje universal de Σ" (pg. 5).
∑* = { λ, a, aa, ab, bc, casa, ... }
1.3 Lenguaje, tipos y herramientas
Lenguaje: Subconjunto del universo del discurso. Conjunto de palabras de un determinado alfabeto. "El alfabeto Σ es también un lenguaje sobre Σ." (Alfonseca, 2006, pg. 6).
Lenguaje vació: Es aquel que no contiene la cadena vacía ni ninguna otra cadena.
Cardinal ( { Ø } ) = 0
Cardinal ( { λ } ) = 1
W(∑) = Lenguaje universal de ∑.
∑+ = W(∑) - { λ }
(Alfonseca, 2006, pg. 6).
Estrella de kleene: Es la unión de todas las potencias de un lenguaje incluso L0. Obviamente, todas las clausuras contienen la palabra vacía. Son evidentes las siguientes identidades:
L0 = λ
Puesto que el alfabeto Σ es también un lenguaje sobre Σ, puede aplicársele esta operación. Se verá entonces que
Clausula (cierre) positiva de un lenguaje: El lenguaje obtenido uniendo el lenguaje L con todas sus potencias posibles, excepto L0. Obviamente, ninguna clausura positiva contiene la palabra vacía, a menos que dicha palabra esté en L. Puesto que el alfabeto Σ es también un lenguaje sobre Σ, puede aplicársele esta operación. Se verá entonces que:
L+ = L1 U L2 U L3....
W(∑) = Lenguaje universal de ∑.
∑+ = W(∑) - { λ }
(Alfonseca, 2006, pg. 6).
Estrella de kleene: Es la unión de todas las potencias de un lenguaje incluso L0. Obviamente, todas las clausuras contienen la palabra vacía. Son evidentes las siguientes identidades:
L0 = λ
L* = L+ U { λ }
L* =L0 U L1 U L2 U L3.....Puesto que el alfabeto Σ es también un lenguaje sobre Σ, puede aplicársele esta operación. Se verá entonces que
∑* = W(∑)
A partir de este momento, representaremos al lenguaje universal sobre el alfabeto Σ con el símbolo Σ*.
(Alfonseca, 2006, pg. 10).
Tipos de lenguajes:
Natural: Los que hablamos los seres humanos. (Alfonseca , 2006, pg. 25).
Artificial: Los lenguajes de programación de computadoras.
- Primera generación: Lenguaje maquina. Los programas se escriben en código binario
- Segunda generación: Lenguajes simbólicos. Cada instrucción de la maquina se representan mediante símbolos
- Tercera generación: Lenguajes de alto nivel. Una sola instrucción de este tipo representa usualmente varias instrucciones de la máquina.
Clasificación de los lenguajes
Chomsky definió cuatro tipos distintos de gramáticas en función de la forma de las reglas de derivación P (Chomsky, 1959). La clasificación comienza con un tipo de gramáticas que pretende ser universal, aplicando restricciones a sus reglas de derivación se van obteniendo los otros tres tipos de gramáticas. Esta clasificación es jerárquica, es decir cada tipo de gramáticas engloba a todos los tipos siguientes.
Gramáticas de tipo 0
También llamadas gramáticas no restringidas o gramáticas con estructura de frase. Las reglas de derivación son de la forma:
∝ → β
Siendo ∝ ε (VN U VT)+ y β ε (VN U VT)*, es decir la única restricción es que no puede haber reglas de la forma λ → β donde λ es la cadena vacía.
Gramáticas de tipo 1
También llamadas gramáticas sensibles al contexto (en ingles context sensitive). En ellas las reglas de producción son de la forma:
∝ A β → ∝ ɤ β
Siendo A ϵ VN; ∝, β ϵ (VN U VT)* y ɤ ϵ (VN U VT)+
Estas gramáticas se llaman sensibles al contexto, pues se puede reemplazar A por ɤ siempre que estén en el contexto ∝ ... β.
La gramatica G = ({S, A, B}, {a,b), S, P) cuyas producciones P se muestran a continuación es de tipo 1.
S → aB
S → bA
A → a
A → aS
A → bAA
B → b
B → bS
B → aBB
Gramática de tipo 2
Las gramáticas de tipo 2 también se denominan gramáticas de contexto libre o libres de contexto (en inglés context free). Sus reglas de producción tan solo admiten tener un símbolo no terminal en su parte izquierda, es decir son de la forma:
A → ∝
Siendo A ϵ VN y ∝ ϵ (VN U VT)+.
Si cada regla se presenta como un par ordenado (A, ∝), el conjunto P es un subconjunto del conjunto producto cartesiano VN x ({ VN U VT })+, es decir:
P ⊂ { N x ( { VN } U { VT } ) + }
La denominación contexto libre se debe a que se puede cambiar A por ∝, independientemente del contexto en que aparezca A.
Ejemplo:
La gramática G = ({S, A, B}, {a,b), S, P) cuyas producciones P se muestran a continuación es de tipo 2.
S → aB
S → bA
A → a
A → aS
A → bAA
B → b
B → bS
B → aBB
Gramáticas de tipo 3
Las gramáticas de tipo 3 también denominadas regulares o gramáticas lineales a la derecha comienzan sus reglas de producción por un símbolo terminal, que puede ser seguido o no por un símbolo no terminal, es decir son de la forma:
A → aB
A → a
Donde A, B ϵ VN y ∝ ϵ VT.
Ejemplo
La gramática G = ({a, b}, {A, S}, S, P) cuyas producciones P se muestran a continuación es de tipo 3.
La gramática G = ({a, b}, {A, S}, S, P) cuyas producciones P se muestran a continuación es de tipo 3.
S → aS
S → aA
A → bA
A → b
Gramática
Es un ente formal para especificar de una manera finita al conjunto de cadenas que constituye un lenguaje. "Una gramática es una cuádrupla." (Cueva Lovelle, 2001).
G = ( VT, VN, S, P )
Donde
VT = { conjunto finito de símbolos terminales }
VN = { conjunto finito de símbolos no terminales }
S es el simbolo inicial y pertenece a VN
P = { conjunto de producciones o de reglas de derivación }
Vocabulario terminal: Se define por enumeración de los símbolos terminales. Todas las cadenas del lenguaje definidos por la gramática están formados con símbolos del vocabulario VT. (Cueva Lovelle, 2001, 7).
Vocabulario no terminal: "VN es el conjunto de símbolos introducidos como elementos auxiliares para la definición de la gramática, y que no figuran en las sentencias del lenguaje. El vocabulario no terminal se define por enumeración de los símbolos no terminales." (Cueva Lovelle, 2001, 7).
La intersección entre el vocabulario terminal y no terminal es el conjunto vacío:
{ VN } ∩ { VT } = { Ø }
La unión entre el vocabulario terminal y no terminal es el vocabulario:
{ VN } ∪ { VT } = { V }
En ocaciones es importante distinguir si un determinado vocabulario incluye o no la cadena vacía, indicándose respectivamente con superíndice + o superíndice *, tal como se muestra a continuación:
V+ = V - { λ }
V* = V + { λ }
(Cueva Lovelle, 2001, 7).
El símbolo inicial S: "Es un símbolo no terminal a partir del cual se aplican las reglas de la gramática para obtener distintas cadenas del lenguaje." (Cueva Lovelle, 2001, 7).
Las producciones P: "Son las reglas que se aplican desde el símbolo inicial para obtener las cadenas del lenguaje. El conjunto de producciones P se define por medio de la enumeracion de las distintas producciones, en forma de reglas o por medio de un metalenguaje por ejemplo BNF (Backus Naur Form) o EBNF (Extended Backus Naur Fourm)." (Cueva Lovelle, 2001, 8).
Cadena válida: Es aquella cadena que cumple con la gramática establecida.
Derivación: "La derivación consiste en tratar a cada producción como una regla de sustitución, donde el símbolo no terminal de la cabecera de una regla se sustituye por la cadena formada por el cuerpo de la producción. El árbol sintáctico se construye a partir de las derivaciones." (Felip Molina, 2009, 17).
7.- Sea la gramática G = ( VT, VN, S, P ) donde VT = { a, b, c, d }, VN = { A, B, C, D, E, I }, S = { I }, P = { 7 } y el conjunto de producciones es:
V+ = V - { λ }
V* = V + { λ }
(Cueva Lovelle, 2001, 7).
El símbolo inicial S: "Es un símbolo no terminal a partir del cual se aplican las reglas de la gramática para obtener distintas cadenas del lenguaje." (Cueva Lovelle, 2001, 7).
Las producciones P: "Son las reglas que se aplican desde el símbolo inicial para obtener las cadenas del lenguaje. El conjunto de producciones P se define por medio de la enumeracion de las distintas producciones, en forma de reglas o por medio de un metalenguaje por ejemplo BNF (Backus Naur Form) o EBNF (Extended Backus Naur Fourm)." (Cueva Lovelle, 2001, 8).
Cadena válida: Es aquella cadena que cumple con la gramática establecida.
Derivación: "La derivación consiste en tratar a cada producción como una regla de sustitución, donde el símbolo no terminal de la cabecera de una regla se sustituye por la cadena formada por el cuerpo de la producción. El árbol sintáctico se construye a partir de las derivaciones." (Felip Molina, 2009, 17).
Ejemplos
1.- Sea la gramática: G = ( VT, VN, S, P ) donde VT = { a, b }, VN = { S }, y el conjunto de producciones es: S → ab y A → aSb
aabb
 |
| Derivación por la izquierda |
 |
| Derivación de árbol |
Se concluye que aabb es una cadena válida ya que se puede derivar de la gramática proporcionada.
2.- Sea la gramática G = ( VT, VN, S, P ) donde VT = { z, a, b }, VN = { M, N, S }, S = { S }, P = { 4 } y el conjunto de producciones es:
S → zMNz
M → aMa
M → z
N → = bNbz
zazabzbz
 |
| Derivación por la izquierda |
 |
| Derivación por la derecha |
 |
| Derivación por árbol |
Se concluye que la cadena proporcionada es una cadena no valida ya que no puede derivarse de la gramática proporcionada.
3.-Sea la gramática G = ( VT, VN, S, P ) donde VT = { a, b }, VN = { S }, S = { S }, P = { 3 } y el conjunto de producciones es:
S → aSbS
3.-Sea la gramática G = ( VT, VN, S, P ) donde VT = { a, b }, VN = { S }, S = { S }, P = { 3 } y el conjunto de producciones es:
S → aSbS
S → bSaS
S → λ
abba
 |
| Derivación por la izquierda |
 |
| Derivación por la derecha |
Se concluye que la cadena es valida ya que pudo ser derivada a partir de la gramática proporcionada.
4.- Sea la gramática G = ( VT, VN, S, P ) donde VT = { a, +, -, *, /, (, ) }, VN = { E, T, F }, S = { E }, P = { 8 } y el conjunto de producciones es:
E → E + T
E → E + T
E → E - T
E → T
T → T * F
T → T / F
T → F
F → ( E )
F → a
 |
| Derivación por la derecha |
 |
| Derivación por la izquierda |
 |
| Derivación de árbol |
5.- Sea la gramática G = ( VT, VN, S, P ) donde VT = { a, b, +, *, (, ) }, VN = { E, T, F }, S = { E }, P = { 7 } y el conjunto de producciones es:
E → E + T
E → T
T → T * F
T → F
F → ( E )
F → a
F → b
 |
| Derivación por la izquierda |
 |
| Derivación por la derecha |
 |
| Derivación por árbol |
Gramática ambigua
Si derivando de forma diferente se llega al mismo resultado (Con el mismo tipo de derivación).
Ejemplos:
6.- Sea la gramática G = ( VT, VN, S, P ) donde VT = { a, b, +, -, *, /, (, ), 0, 1, 2... }, VN = { E, N, I }, S = { E }, P = { 9 } y el conjunto de producciones es:
E → E + E
E → E * E
E → E - E
E → E / E
E → ( E )
E → ( E )
E → I
E → N
N → 0 | 1 | 2 | ...
I → a | b
 | ||
Derivación por la izquierda
|
7.- Sea la gramática G = ( VT, VN, S, P ) donde VT = { a, b, c, d }, VN = { A, B, C, D, E, I }, S = { I }, P = { 7 } y el conjunto de producciones es:
I → A | B
A → CD
C → cd | aCb
C → ab | aCb
D → cd | cDd
B → aBd | aEd
D → cd | cDd
B → aBd | aEd
E → bc | bEc
 |
| Derivación por la izquierda |
 |
| Derivación por la izquierda |
1.4 Estructura de un 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. |
En el proceso de traducción se identifican dos faces principales:
1.5 Fases de un compilador
Fase de análisis
Fase de síntesis
Fuentes
- Alfonseca Moreno, M., De la Cruz Echeandía, M., Ortega de la Puente, A., & Pulido Cañabate, E. (2006). Compiladores e interpretes: teoría y práctica. Madrid, España: Pearson: Prentice Hall.
- Brena, R. (2003). Automatas y lenguajes. Monterrey.
- Cueva Lovelle, J. M. (2001). Lenguajes gramáticas y autómatas. Oviedo, España.
- Felip Molina, L. (2009). Generador de compiladores basado en analizadores ascendentes. Barcelona, España: Universidad autónoma de Barcelona.
Comentarios
Publicar un comentario