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

NE111 · miércoles 07/10/2026 · 16:00-17:15 · Sesión 17

Expresiones regulares

DESCRIBIR EN VEZ DE RECONOCER

Una expresión regular describe un lenguaje mediante una fórmula. Es la contraparte declarativa de los autómatas, que lo reconocen operacionalmente. Ambas capturan exactamente la misma clase.

DEFINICIÓN INDUCTIVA

Casos base:

• ∅ es una ER que denota el lenguaje vacío.
• ε es una ER que denota {ε}.
• a es una ER que denota {a}, para cada a ∈ Σ.

Casos inductivos: si r y s son ER, también lo son r+s (unión), rs (concatenación), r* (estrella) y (r).

Es otra definición recursiva, la tercera del curso. Y como toda definición recursiva, trae asociado su principio de inducción estructural para demostrar propiedades.

PRECEDENCIA

La estrella liga más fuerte que la concatenación, y ésta más que la unión. Así ab*+c se lee (a(b*))+c. Ante la duda, paréntesis.

EJEMPLOS SOBRE {0,1}

• (0+1)* — todas las cadenas.
• (0+1)*01 — las que terminan en 01.
• 0*10*10* — las que tienen exactamente dos unos.
• (0+1)*11(0+1)* — las que contienen 11.
• (01)* — alternancias que empiezan en 0 y terminan en 1, más ε.

IDENTIDADES ÚTILES

• r + ∅ = r · r∅ = ∅ · rε = r
• (r*)* = r* · ∅* = ε · (ε + r)* = r*
• r(s + t) = rs + rt

DÓNDE SE USAN DE VERDAD

Búsqueda de patrones, validación de formatos, y sobre todo la especificación de los componentes léxicos de un lenguaje de programación, que es a donde va este bloque.

ADVERTENCIA SOBRE LAS REGEX DE LOS LENGUAJES

Las expresiones regulares de Perl, Python o JavaScript incluyen retroreferencias y lookahead, que exceden lo que un autómata finito puede reconocer. Formalmente ya no son expresiones regulares. Es un abuso de nombre cómodo, pero en este curso la distinción importa.

EJERCICIO

Escribir ER para: número par de ceros; que no contenga 101; longitud múltiplo de 3; identificadores válidos de un lenguaje de programación.