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.
En el proceso de traducción se identifican dos fases principales:
es un conjunto de cadenas sobre un alfabeto 
definido, éstas pueden ser cualquier cadena 
, que cumpla con lo siguIente, 
donde 
.
, éste lenguaje se denota de la misma manera que el conjunto vacío, 
.
, entonces diremos que 
.
, entonces 
y es una secuencia vacía de símbolos tomados de cualquier alfabeto 
, 
y 
. Dada la definición anterior, cualquier palabra que contenga los símbolos del alfabeto es una cadena válida, sin importar si esta tiene o no significado alguno.
, la longitud de una cadena es el número de símbolos que contiene, por ejemplo, si tenemos la cadena 
sobre el alfabeto español, 
. La cadena vacía 