ALFABETO

                                          Alfabeto

Definición (Alfabeto):

Conjunto finito, no vacío, de elementos.
Generalmente usaremos Σ para especificar alfabetos y los elementos los denominaremos “letras” o “símbolos”.

Ejemplos:

los alfabetos español, inglés, o alemán

Σ1={0,...,9}, 0∈Σ1

Σ2={x | x es un símbolo del código ASCII}

Σ3={(, )}

Σ4={1, A, 2, B}

Σ5={a, b, c, d}

Σ6={}

Σ7=ℵ

Definición (Palabra):

Sea un alfabeto Σ. Una palabra sobre Σ es una secuencia finita de las letras de ese alfabeto.
La secuencia vacía representa la palabra vacía y la anotamos con λ.

Ejemplos: sobre Σ5 ={a,b,c,d}: λ, a, b, c, d, abc, aab, dcba, ... sobre Σ1 ={0,...,9}: λ, 0, 0000, 010, 9980, ... sobre Σ3 ={(,)} λ, (, ), (), (()()), )())), ...

Definición (Longitud de una palabra):

Se llama longitud de una palabra x, y se representa por |x|, al número de símbolos que la componen.

Ejemplos: sobre Σ5 ={a,b,c,d}: |λ|=0, |a|=1, |abc|=3

Definición (Concatenación):

Sean dos palabras x e y definidas sobre el alfabeto Σ. La concatenación de x e y, denominada “xy”, es una palabra que contiene todos los símbolos (de derecha a izquierda) de x seguidos de los símbolos de y (de derecha a izquierda).
Sean x=A1A2...An e y=B1B2...Bm con Ai, Bi ∈ Σ: ⇒ xy= A1A2...AnB1B2...Bm

Ejemplos: x =abc, y =da, definidos sobre Σ={a,b,c,d} xy=abcda ; |xy|=|x|+|y|=5

Definición (Potencia):

Sea i un número natural, y x una palabra. La potencia i-ésima de x, denominada xi, es la operación que consiste en concatenarla consigo misma i veces.

Ejemplos: x =abc ⇒ x1=abc x2=abcabc x3=abcabcabc

Definición (Palabra inversa):

Sea x=A1A2...An con Ai∈Σ una palabra sobre el alfabeto Σ. Se llama palabra refleja o inversa de x, y se representa por x-1, a la palabra AnAn-1...A1. Si x=λ entonces x-1=λ.

Ejemplos: x =abc ⇒ x-1=cba

Definición (Lenguaje universal):

Sea Σ un alfabeto. El lenguaje universal de Σ es el conjunto formado por todas las palabras que se pueden formar con las letras de Σ. Representamos dicho lenguaje con W(Σ).

Ejemplos: 

Σ1 ={a} ⇒ W(Σ1)={λ, a, aa, aaa, ...}

Definición (Lenguaje):

Sea un alfabeto Σ. Un lenguaje L sobre Σ es cualquier subconjunto del lenguaje universal W(Σ).

Ejemplos: Σ1 ={a} ⇒ W(Σ1)={λ, a, aa, aaa, ...} L1 ={a} ⊆ W(Σ1) L2 ={} ⊆ W(Σ1) (L2 = ∅) L3 =Σ1 ⊆ W(Σ1) L4 =W(Σ1) ⊆ W(Σ1) L5 ={λ} ⊆ W(Σ1) (Nota: L5≠L2) L6 ={λ, a, aaa, aaaaa} ⊆ W(Σ1) L7 ={λ, a, aaa, aaaaa, ...} ⊆ W(Σ1)

Hay lenguajes finitos, infinitos y vacíos.