Lenguajes Regulares, Expresiones Regulares y Autómatas Finitos
Enviado por Programa Chuletas y clasificado en Informática y Telecomunicaciones
Escrito el en español con un tamaño de 10,7 KB
Lenguajes sobre Alfabetos
Consideremos el alfabeto Σ = {a, b}. Para todo número natural n, hay solo un número finito de palabras sobre Σ cuya longitud es n. Dichas cadenas se pueden obtener lexicográficamente. Numeramos Σ como 0, después numeraremos las palabras de longitud 1, y en general las de longitud n+1 después de las de longitud n. Por ejemplo: Σ -> 0, a -> 1, b -> 2, aa -> 3, ab -> 4...
- De manera más general, suponiendo que tenemos un alfabeto arbitrario Σ. Puesto que todos los alfabetos son finitos, podemos asignar un orden arbitrario a los caracteres pertenecientes a Σ. Así, sin pérdida de generalidad, podemos escribir Σ = {a0, a1, a2...an} y numeramos las palabras de Σ de la misma forma: Σ -> 0, a1