Para empezar con esto, veremos antes ¿Qué es un lenguaje desde un punto de vista completamente matemático?

Para definir un lenguaje  (que es la parte fundamental de la teoría de autómatas) tenemos que definir algo más elemental, un alfabeto:

Un Alfabeto

Un alfabeto es finito (y que obviamente no esta vacío, sino no tiene sentido) de forma común usamos el símbolo de suma.

Algunos alfabetos comunes son:

• El Alfabeto Binario
• El Alfabeto ASCII

Strings – Cadenas

Un string o una palabra es una secuencia finita de símbolos de un alfabeto. Por ejemplo, 01101 es una cadena del alfabeto binario. La cadena 111 es otra cadena de este alfabeto.

Cadena Vacía: Hay una cadena muy especial y que siempre tiene que existir, y es un string sin ningún símbolo.

Longitud de un String

A menudo es útil clasificar cadenas por su longitud, es decir, el número de símbolos en la cadena. Por ejemplo, 01101 tiene longitud 5.  La notación estándar para la longitud de una cadena:

Potencias de un Alfabeto

Si tenemos un alfabeto cualquiera, podemos expresar el conjunto de todas las cadenas de una cierta longitud usando la notación de potencia.

Así elevar un alfabeto a una potencia K es lo mismo que preguntar por todos los posibles strings con longitud K.

De aquí podemos sacar la gran pregunta, ¿Cuál es la diferencia entre el la segunda y la tercera línea? El primero es un alfabeto; sus miembros 0 y 1 son símbolos. El segundo es un conjunto de strings cual longitud son uno.

Así para denotar el conjunto de todos los posible strings usamos:

A veces es útil excluir a la cadena vacía, por lo que tenemos la siguiente notación y propiedades:

Lenguajes

Un conjunto de cadenas de todo el universo posible es lo que llamamos un lenguaje. Es decir:

No es necesario incluir todas las cadenas posibles, solo un conjunto de ese conjunto enorme que tenemos para elegir.

La elección del término «lenguaje» puede parecer extraña. Sin embargo, los idiomas se pueden ver como conjuntos de cadenas. Un ejemplo es el inglés, donde la colección de palabras es un conjunto de cadenas sobre el alfabeto que consiste de todas las letras. Otro ejemplo es C, o cualquier otro lenguaje de programación.

Aquí otros ejemplos:

• El lenguaje binario donde todos los strings tienen las mismas cantidades de unos y ceros.
• El lenguaje binario donde todos los strings son K unos seguidos de K ceros.

La única restricción importante en lo que puede ser un lenguaje es que todos los alfabetos son finitos. Así aunque un lenguaje puede tener un número infinito de cadenas, solo puede sacarlos de un numero finito de símbolos.