Automatas

Lenguajes y
gramática
Carlos Alfonso Lozano

Alfabeto.
conjunto no vacío y finito de símbolos. A estos símbolos
también se les suele llamar letras del alfabeto. Se
denota con la letra griega Σ. Ejemplos:
 Σ1  = {a,b,c,d,e,f,j…..z}
 Σ2  = {0, 1}
 Σ3  = {na, pa, bra, la}
 Σ4  = {, , , , . . .}
 Σ5  = {|}
 Σ6  = {a, ab, aab}

…
 Usamos subíndices para distinguirdiferentes

alfabetos.
 Usamos normalmente las minúsculas como

alfabeto Σ = {a, . . . , z}, en los ejemplos
normalmente letras desde el principio del
alfabeto.
 Cardialidad

del
alfabeto
(número
de
elementos del alfabeto): |Σ| > 0, |Σ| < ∞ .
Ejemplo:

 Σ={0,1,2} |Σ|=3

Potencias de un
alfabeto

Si Σ es un alfabeto, podemos expresar el conjunto
de todas las cadenas de una determinada
longitud dedicho alfabeto utilizando una notación
exponencial. Definimos Σelevado a la k para que
sea el conjunto de las cadenas de longitud k,
tales que cada uno de los símbolos de las mismas
pertenece a Σ. Por ejemplo:
 Si Σ = {0,1}, entonces Σ elevado a la 1 =

{0,1}, Σelevado a la 2 = {00,01,10,11},
Σelevado
a
la
3
=
{000,001,010,011,100,101,110,111}

Palabras
secuencia finita de símbolos de unalfabeto. Lo
correcto es hablar de “palabras definidas sobre
un alfabeto”. Habitualmente utilizaremos en
nuestros ejemplos las últimas letras minúsculas
de nuestro alfabeto (x, y) para denotar a las
palabras. Ejemplos:
 x = casa es una palabra definida sobre el

alfabeto Σ1
 y = 010100 es una palabra definida sobre el

alfabeto Σ2

Operaciones con
palabras

En este apartado se presenta una colecciónde
operaciones que se pueden realizar con palabras
y
las
propiedades
que
cumplen
estas
operaciones.
 Concatenación Sean x e y dos palabras, se

concatenan para formar otra palabra que se
denota xy y que esta formada por todas las
letras de x seguidas por las letras de y.
Ejemplo:
x= casa y=blanca ⇒xy = casablanca

…
Propiedades:

1. Operación cerrada. Si x e y están definidas sobre

el mismoalfabeto, xy también lo estará.
2. Asociativa. (xy)z = x(yz)
3. Elemento neutro (λ). xλ = λx = x
4.

|xy| = |x| + |y|

5. No es una operación conmutativa

…
 Potencia i-esima de una palabra (xi) consigo

misma, i veces. X elevado a la i = x...i x
Ejemplo: x = la ⇒ x elevado a la 4 = lalalala
Propiedades:
1. X elevado a la i+j = x elevado a la i x elevado a laj
2. |x elevado a la i| = i|x|
3. Xelevado a la 0 = λ

…
. Reflexión (o inversa) de una palabra (x

elevado a la−1) Es otra palabra definida sobre
el mismo alfabeto y formada por los mismos
símbolos que x, dispuestos en orden inverso.
Ejemplo: x = casa ⇒ x elevado a la −1 = asac
Propiedad:
1. |x| = |x elevado a la −1| (Elena jurado

Málaga, 2008)

Definición formal de
lenguaje

Un
conjunto
de
cadenas,
todas
ellas
seleccionadas de unΣ∗, donde Σ es un
determinado alfabeto se denomina lenguaje. Si
Σ es un alfabeto y L ⊆ Σ∗, entonces L es un
lenguaje de Σ. Observe que un lenguaje de Σ no
necesita incluir cadenas con todos los símbolos
de Σ, ya que una vez que hemos establecido
que L es un lenguaje de Σ, también sabemos
que es un lenguaje de cualquier alfabeto que
sea un súper conjunto de Σ.

…
La elección del termino“lenguaje” puede
parecer extraña. Sin embargo, los lenguajes
habituales pueden interpretarse como conjuntos
de cadenas. Un ejemplo sería el inglés, donde la
colección de las palabras correctas inglesas es
un conjunto de cadenas del alfabeto que consta
de todas las letras. Otro ejemplo es el lenguaje
C, o cualquier otro lenguaje de programación,
donde los programas correctos son un
subconjunto de las posiblescadenas que
pueden formarse a partir del alfabeto del
lenguaje.

…
 Este alfabeto es un subconjunto de los

caracteres ASCII. El alfabeto en concreto
puede diferir ligeramente entre diferentes
lenguajes de programación, aunque
generalmente incluye las letras mayúsculas y
minúsculas, los dígitos, los caracteres de
puntuación y los símbolos matemáticos.
(JOHN E. HOPCROFT, RAJEEV MOTWANI,...