1_Lenguajes_formales - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

1 
 
LENGUAJES 
FORMALES 
 
 
2 
 
Definiciones básicas 
Alfabeto: Conjunto finito no vacío cuyos elementos se llaman símbolos o letras. Se denota 
con la letra griega Σ. 
Ejemplos: 
Σ1 = {a,b,c}, el alfabeto que consta de tres símbolos, a, b y c. 
Σ2 = {0,1}, el alfabeto que consta de dos símbolos, 0 y 1 
 
Palabra: Una palabra o cadena sobre un alfabeto Σ es cualquier sucesión finita de 
elementos de Σ. 
Ejemplos: 
u = abbca es una palabra definida sobre el alfabeto Σ1 
w = 1101101 es una palabra definida sobre el alfabeto Σ2 
 
Palabra vacía: es una palabra que no tiene ningún símbolo y se representa como λ ó ε 
 
Longitud de palabra: es el número de símbolos que componen una palabra. Se representa 
utilizando dos barras verticales (||). 
Ejemplos: 
|u|=5 
|w|=7 
|λ|=0 
 
Lenguaje universal: Se denota por Σ* y es el conjunto de todas las palabras que se pueden 
construir con las letras de un alfabeto Σ, incluyendo la palabra vacía. El lenguaje universal 
de cualquier alfabeto es infinito y siempre pertenece a él la palabra vacía. 
Ejemplo: 
Sea Σ = {a,b,c}, entonces Σ*= {λ,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,abc,baa,...} 
 
Lenguaje: Un lenguaje L definido sobre un alfabeto Σ, es un conjunto cualquiera de 
palabras definidos sobre dicho alfabeto, por lo tanto L ⊂ Σ* ó L ⊆ Σ* 
Ejemplo: 
Sea Σ={a,b}, podemos definir diferentes lenguajes sobre ese alfabeto: 
L1 = { |x|=4 } 
L2 = { a
nbn | n>0 } 
L3 = { x | x no contenga un número par de a’s } 
 
Lenguajes especiales: 
Lenguaje vacío que se representa como LØ = Ø y que no tiene ninguna palabra. 
Lenguaje lambda que se representa como Lλ = {λ} y que contiene solamente la palabra 
vacía. 
 
 
3 
 
Operaciones con palabras 
Concatenación 
Si x y y son palabras, la concatenación x·y es una palabra formada por los símbolos de x 
seguidos de los símbolos de y. En general se representa simplemente como xy. 
Ejemplo: 
x = pa, y = labra ⇒ xy = palabra 
 
Propiedades 
Operación cerrada: Si x y y están definidas sobre el mismo alfabeto, xy también lo estará. 
Asociativa: (xy)z = x(yz) 
Elemento neutro (λ). xλ = λx = x 
|xy| = |x| + |y| 
No es una operación conmutativa xy ≠ yx 
Potencia 
La potencia i-ésima de una palabra x, xi, se forma por la concatenación i veces de x. 
xi = x·x·….. · x , es decir, x4 = x·x·x·x, x3= x·x·x, etc. 
 
 i 
Ejemplo: 
x = la ⇒ x4 = lalalala 
y = 01 ⇒ x2 = 0101 
 
Propiedades 
xi+xj = xixj 
|xi| = i|x| 
x0 = λ 
Reflexión (o inversa) de una palabra 
Si la palabra x está formada por los símbolos s1,s2….sn, entonces la inversa de x, x
-1, se 
forma por los mismos símbolos dispuestos en orden inverso, x-1 = sn …s2,s1 
Ejemplo: 
x = casa ⇒ x−1 = asac 
y = 01 ⇒ y-1 = 10 
 
Propiedad: 
|x|=|x−1| 
Operaciones con lenguajes 
Unión 
La unión de dos lenguajes L1 y L2 es otro lenguaje que contiene todas las palabras de L1 y 
todas las palabras de L2. 
L1 U L2 = { x | x ∈ L1 ∨ x ∈ L2 } 
 
 
4 
 
Ejemplo: 
Sea L1 = { aba, bb, bba, ba } y L2 = { λ, aa, bb, ab, ba } entonces L1 U L2 = { λ , aa, bb, ab, ba, 
aba, bba } 
 
Propiedades 
Operación cerrada: El lenguaje resultante está definido sobre el mismo alfabeto que L1 y 
L2. 
Asociativa: (L1 ∪ L2) ∪ L3 = L1 ∪ (L2 ∪ L3) 
Conmutativa: L1 ∪ L2 = L2 ∪ L1 
Elemento Neutro (Ø): L ∪ Ø = Ø ∪ L = L 
Idempotencia. L ∪ L = L 
Intersección 
La intersección de dos lenguajes L1 y L2 es otro lenguaje que contiene todas las palabras 
que pertenecen a los dos lenguajes. 
L1 ∩ L2 = { x | x ∈ L1 ˄ x ∈ L2 } 
Ejemplo: 
Sea L1 = { aba, bb, bba, ba } y L2 = { λ, aa, bb, ab, ba } entonces L1 ∩ L2 = { bb, ba } 
 
Propiedades 
Operación cerrada: El lenguaje resultante está definido sobre el mismo alfabeto que L1 y 
L2. 
Asociativa: (L1 ∩ L2) ∩ L3 = L1 ∩ (L2 ∩ L3) 
Conmutativa: L1 ∩ L2 = L2 ∩ L1 
Idempotencia. L ∩ L = L 
L ∩ ∅ = ∅ 
Concatenación 
La concatenación de dos lenguajes L1 y L2 es otro lenguaje que contiene todas las palabras 
que se pueden formar por la concatenación de una palabra de L1 y otra de L2 
L1 · L2 = { xy | x ∈ L1 ˄ y ∈ L2 } 
Ejemplo: 
Sea L1 = { aba, bb, bba, ba } y L2 = { λ, aa, bb, ab, ba } entonces L1 · L2 = { aba, abaaa, ababb, 
abaab, ababa, bb, bbaa, bbbb, bbab, bbba, bba, bbaaa, bbabb, bbaab, bbaba, ba, baaa, 
babb, baab, baba } 
 
Propiedades 
Operación cerrada: El lenguaje resultante de concatenar dos lenguajes está definido sobre 
el mismo alfabeto. 
Asociativa: (L1 L2) L3 = L1 (L2 L3) 
Elemento Neutro (λ): LλL=L Lλ= L 
No es conmutativa 
 
 
 
5 
 
Potencia 
La potencia i-ésima de un lenguaje L, Li, corresponde a la concatenación i veces del 
lenguaje con él mismo. 
Li = L·L·….. · L 
 
 i 
Ejemplo: 
Sea L = {0,1} entonces L2 = {00,01,10,11} 
 
Propiedades 
Li+j = LiLj 
L0 = Lλ = {λ} 
Clausura o cierre de Kleene 
La clausura de un lenguaje L, se denota por L* y es el resultado de unir todas las potencias 
de dicho lenguaje. 
 
Clausura positiva 
La clausura positiva de un lenguaje L, se denota por L
+
 y es el resultado de unir todas las 
potencias de dicho lenguaje, excepto la potencia 0 
 
Ejemplo: 
Sea L = {0,1} entonces 
L+ = { 0,1,00,01,10,11,000,001…. } 
L* = { λ, 0,1,00,01,10,11,000,001…. } 
 
Propiedades 
L* = L+ U {λ} 
L+ = L*L = LL* 
L+ = L* - {λ} 
Reflexión 
La reflexión de un lenguaje L, denotado por L-1, está formada por las inversas de todas las 
palabras de ese lenguaje. 
L-1 = { x-1 | x ∈ L} 
Ejemplo: 
Sea L = {0,1,00,10} entonces L-1 = {0,1,00,01} 
 
 
6 
 
Complemento 
El complemento de un lenguaje L definido sobre un alfabeto Σ, se denota por L y 
contiene todas las palabras del lenguaje universal Σ* que no pertenecen a L. 
L = Σ* - L = { x | x ∈ Σ* y x ∉ L } 
 
Propiedades: 
 Σ* = ∅ 
L = L 
 L ∩ L = ∅ 
 L U L = Σ*