Lenguajes y Autómatas - Módulo 1.1 (Alfabetos, cadenas y lenguajes)

Introducción a Alfabetos, Cadenas y Lenguajes

Conceptos Fundamentales

• Se presenta el tema del curso sobre lenguajes y autómatas, enfatizando la importancia de entender los fundamentos de la lingüística en relación con los lenguajes de programación.

• Se define un alfabeto como un conjunto no vacío de símbolos o caracteres, denotado por Sigma (Σ), cuya cardinalidad es mayor que cero.

• Ejemplos de alfabetos incluyen el alfabeto español (a-z, ñ) y el alfabeto binario (0, 1). También se menciona el alfabeto hexadecimal utilizado en codificaciones como HTML.

Palabras y Cadenas

• Los símbolos de un alfabeto se combinan para formar palabras o cadenas. Una cadena es una yuxtaposición de elementos del alfabeto.

• La palabra vacía se denota con épsilon (ε), siendo la única cadena posible de tamaño cero. El largo de una palabra se mide por su número de símbolos.

Combinaciones y Notaciones

• Se introduce la notación Σ^n para representar todas las combinaciones posibles de longitud n. Por ejemplo, Σ^0 solo tiene la cadena vacía.

• La clausura de Kleene (Σ*) incluye todas las cadenas posibles construidas a partir del alfabeto dado, mientras que Σ+ excluye la palabra vacía.

Concatenación y Estructura

• Al concatenar palabras se pueden formar nuevas cadenas más largas. Esto es común en idiomas como el alemán o español con palabras compuestas.

• Se explica cómo determinar prefijos, sufijos y subcadenas dentro de una cadena dada. Por ejemplo, en "0110", "0" es un prefijo y "10" puede ser considerado un sufijo.

Definición de Lenguaje

Operaciones sobre Lenguajes Formales

Concatenación de Lenguajes

• Se puede concatenar dos lenguajes, denotados como L1 y L2, formando un nuevo conjunto de cadenas que combina elementos de ambos.

Disyunción de Lenguajes

• La operación de disyunción permite considerar cadenas que pertenecen a uno u otro lenguaje, representado por el conjunto de cadenas X donde X pertenece a L1 o L2.

Potencia de un Lenguaje

• La operación potencia se representa con superíndices; por ejemplo, L^k es la concatenación del lenguaje con palabras de tamaño uno multiplicado por L^(k-1).

Clausura y Complemento

• La clausura se refiere a la unión de los lenguajes elevados a diferentes potencias (L^0, L^1, etc.). El complemento toma todas las combinaciones posibles en un alfabeto dado y resta el lenguaje considerado.

Ejemplo en Programación