GUÍA 05-10-26 Teoría de la Computación

NE111 · lunes 05/10/2026 · 16:00-17:15 · Sesión 16

Alfabetos, cadenas y lenguajes

BAJAMOS DE NIVEL

Terminado el bloque de los límites, empieza el de los modelos que sí se construyen. Para eso hace falta primero el vocabulario formal sobre el que se definen los lenguajes.

ALFABETO

Un alfabeto Σ es un conjunto finito y no vacío de símbolos. Σ = {0,1} para el binario, Σ = {a,…,z} para texto. La finitud es esencial.

CADENA

• Secuencia finita de símbolos de Σ.
• Longitud |w| — número de símbolos. |01101| = 5.
• Cadena vacía ε — la de longitud 0. Existe sobre cualquier alfabeto.

ε no es lo mismo que el conjunto vacío ∅, ni que un espacio en blanco. Confundirlos es el error más común del tema.

OPERACIONES SOBRE CADENAS

• Concatenación: si w = 01 y v = 10, entonces wv = 0110. No es conmutativa.
• ε es el neutro: wε = εw = w.
• Potencia: w⁰ = ε y wⁿ = w·wⁿ⁻¹. Es una definición recursiva, como las de la sesión 8.
• Reverso: (01101)ᴿ = 10110.

Σ* Y Σ⁺

• Σ* — todas las cadenas sobre Σ, incluida ε. Es infinito numerable.
• Σ⁺ = Σ* − {ε}.

LENGUAJE

Un lenguaje L es cualquier subconjunto de Σ*. Puede ser finito o infinito, y definirse por enumeración o por comprensión.

• L = {0ⁿ1ⁿ | n ≥ 0} = {ε, 01, 0011, 000111, …}
• ∅ es un lenguaje y {ε} es otro distinto: el primero no tiene cadenas, el segundo tiene una.

OPERACIONES SOBRE LENGUAJES

• Unión, intersección y complemento, heredadas de los conjuntos.
• Concatenación: L₁L₂ = {xy | x ∈ L₁, y ∈ L₂}.
• Cerradura de Kleene: L* = L⁰ ∪ L¹ ∪ L² ∪ … Siempre contiene ε.
• L⁺ = L·L*, que contiene ε solo si L lo contiene.

LA OPERACIÓN QUE GENERA INFINITUD

Con L = {01}, L* = {ε, 01, 0101, …} es infinito aunque L tenga una sola cadena. La estrella es la única operación que produce conjuntos infinitos a partir de finitos, y por eso es la pieza central de las expresiones regulares.

EJERCICIO

Escribir por comprensión: cadenas binarias de longitud par; con igual número de ceros y unos; que empiezan y terminan con el mismo símbolo.