Automatas

Alfabetos y lenguajes

Empezamos con la idea de un alfabeto: un conjunto finito de símbolos del sistema operativo. Un ejemplo es, naturalmente, el alfabeto latino (a, b ,..., z). Un alfabeto enparticular perteneciente a la teoría de la computación es el alfabeto binario (0,1). De hecho, cualquier objeto puede estar en un alfabeto, desde un punto de vista formal, un alfabeto es simplemente unconjunto finito de cualquier tipo. Para simplificar, sin embargo, que usamos como símbolos, sólo letras, números y otros caracteres no común, conviene, como $ o #.
Una cadena más de un alfabeto esuna secuencia finita de símbolos del alfabeto. En lugar de escribir cadenas con paréntesis y comas, como hemos escrito otra secuencia, simplemente se yuxtaponen los símbolos. Así, la sandía es unacadena sobre el alfabeto (a, b ,..., z), y 0111011 es una cadena de más de (0,1). Además, mediante el isomorfismo natutal, identificamos una serie de sólo un símbolo con el símbolo de sí mismo, por lotanto el símbolo a es la misma que la cadena a. Una cadena puede no tener a todos los símbolos, en este caso se denomina la cadena vacía y se denota por e. Por lo general, el uso u, v, x, y, z, y letrasgriegas para referirse a las cadenas, por ejemplo, podríamos usar w como un nombre para la cadena abc. Por supuesto, para evitar la confusión es una buena práctica de abstenerse de utilizar símboloscomo las letras que también su uso como nombres de cadenas. El conjunto de todas las cadenas, incluyendo la cadena vacía, más de un alfabeto ∑ se denota por ∑*.

La longitud de una cadena es sulongitud, como una secuencia, por lo tanto la longitud de la cadena de acrd es 4. Nos indican la longitud de una cadena de W | W |, por lo tanto | 101 | = 3 y | e | = 0. Otra opción (es decir, a través deun isomorfismo natural) una cadena de w є∑* puede ser considerada como una función w: (1 ,...,| w |) -> ∑, el valor de w (j ), donde 1 <= j <= | w |, es el símbolo en la posición j de W....