Lenguages formales

UNIDAD 6 INTRODUCION A LOS LENGUAJES FORMALES
6.2gramatica y lenguajes

Alfabetos y palabras
Un alfabeto es un conjunto finito y no vacío de elementos llamados símbolos o letras. Una palabra o cadena sobre un alfabeto V es una cadena finita de símbolos del alfabeto. La longitud de una cadena w, que notaremos como |w|, es el numero de letras que aparecen en w. A la cadena que no tienesímbolos, o lo que es lo mismo, que tiene longitud 0, la llamaremos palabra vacía y se nota por λ (o también ǫ, según los autores).
Si V es un alfabeto, llamaremos V n al conjunto de todas las palabras de longitud n sobre V .
Un elemento de V n será una cadena del tipo a1a2 . . . an donde cada ai ∈ V . Llamaremos V 0 al conjunto cuyo ´único elemento es la palabra vacía, es decir, V 0 = {λ} . El conjuntode todas las Cadenas de cualquier longitud sobre V es:
V ∗ =∞[n=0V n

Llamamos V + al conjunto de todas las cadenas sobre el alfabeto V excepto la vacía. Por tanto,
V + = V ∗ − {λ}.

6.2.1 Estructuras de las gramáticas

1.1. Concatenación de Palabras
La operación de concatenación, que notaremos ‘・’, es una operación binaria entre palabras sobre Un alfabeto V, esto es:
・ : V ∗ × V ∗ −→ V∗

De forma que si tenemos dos palabras x, y ∈ V ∗ donde x = a1a2 . . . an, y = b1b2 . . . bm entonces, x concatenado con y será una palabra w ∈ V ∗ con |w| = |x| + |y|, de forma que:
w = x ・ y = a1a2 . . . anb1b2 . . . bm¨§¥
¦
Nota A veces se suele suprimir el ‘・’ y se puede escribir directamente w = xy
Algunas propiedades de la concatenación son:
operación cerrada 99K ∀ x, y ∈ V ∗ : x ・ y ∈V ∗
Propiedad asociativa 99K ∀ x, y, z ∈ V ∗ : x ・ (y ・ z) = (x ・ y) ・ z
elemento neutro λ 99K ∀ x ∈ V ∗ : λ ・ x = x ・ λ = x
Por tener estas propiedades (V ∗, ・, λ) es un monoide. Además cada palabra de V ∗ se representa De forma ´única como concatenación de símbolos de V , por eso es además un conoide libre.
Todo monoide libre cumple la ley de cancelación izquierda y derecha, en este caso, ∀x, y, z ∈
V se cumple que:
(X ・ y = x ・ z) ⇒ (y = z) k (y ・ x = z ・ x) ⇒ (y = z)
Decimos que una cadena z es subcadena de otra cadena w si existen cadenas x, y ∈ V ∗ tal que
w = x ・ z ・ y. Vamos a ver dos conjuntos especiales de subcadenas:
Prefijo (w) = {x ∈ V ∗ | ∃ z ∈ V ∗ : w = x ・ z} k Sufijo (w) = {x ∈ V ∗ | ∃ z ∈ V ∗ : w = z ・ x}
Diremos que x es un prefijo de w si x ∈Prefijo (w) ysera un prefijo propio si x 6= w. Por otra
Parte, diremos que x es un sufijo de w si x ∈Sufijo (w) y sera un sufijo propio si x 6= w.
Ejemplo 1.1 Si w = abab es una palabra sobre el alfabeto {a, b}, o lo que es lo mismo, w ∈
{a, b}∗, teneos que:
ab es un prefijo propio de w
abab es un prefijo de w, pero no es propio
b es un sufijo de w

1.2. Potencia de una palabra
Llamamos potencian-´esima de una palabra, a la operación que consiste en concatenar la palabra Consigo misma n veces. Dada una palabra w ∈ V ∗, se define inductivamente la potencia n-´esima de w, que notaremos wn, como:
1. w0 = λ
2. wn = w ・ wn−1 para n > 0
Ejemplo 1.2 Si w = aba es una palabra sobre el alfabeto {a, b} entonces:
w0 = λ
w1 = aba
w2 = abaaba
16
1.3. Inversi´on de palabras
Si w = a1a2 . . . an esuna palabra sobre un alfabeto V entonces la palabra inversa o refleja de
w se define como: wR = anan−1 . . . a1
Ejemplo 1.3 Si w = aaba es una palabra sobre el alfabeto {a, b}, entonces wR = abaa.

2. Lenguajes formales
Llamamos lenguaje sobre el alfabeto V a cualquier subconjunto de V ∗. Así tenemos que,
V ∗,? , y V pueden considerarse como lenguajes. Puesto que un lenguaje es tan solo unaclase
especial de conjunto, podemos especificar un lenguaje finito por extensión enumerando sus elementos entre llaves. Por ejemplo, {aba, czr, d, f} es un lenguaje sobre el alfabeto {a, b, c, ..., z}.Sin embargo, la mayoría de los lenguajes de interés son infinitos. En este caso podemos especificar un lenguaje por comprensión de la siguiente forma:
L = {w ∈ V ∗ | w cumple la propiedad P}...