sistemas

Oliver A. Vilca H.

Pág. 1

Expresiones regulares y autómatas finitos

dor

Resumen de clases
Oliver Amadeo Vilca Huayta

Una expresión regular sirve como un descriptor de un lenguaje, también es una herramienta para
describir patrones de texto, por ejemplo:
1. Se utiliza una notación similar a una expresión regular para describir patrones de búsqueda.
Por ejemplo en el procesamientode documentos electrónicos, bioinformática, base de datos y en
comandos de búsqueda como el GREP de UNIX.
2. En los generadores de analizadores léxico como el Lex y el Flex. El análisis léxico es una fase de
un compilador que divide el código de entrada en unidades lógicas denominadas tokens de uno
o más caracteres. Ejemplos de tokens son las palabras reservadas (ejemplo: if ), identificadoresy signos como +,>.
3. En búsqueda de texto flexible, se utiliza la expresión regular como un patrón de búsqueda, por
ejemplo: a??bc[f-p] puede represetar a todas las cadenas (palabras) de texto que inician con la a
seguida de cualquier dos carateres (símbolos), seguida de bc, y, finalmente un carater que puede
ser desde la f hasta la k, es decir, uno del rango de carateres comprendido entre laf y k.

Bor
ra

Una ventaja adicional es que se puede convertir en una máquina (autómata finito), el cual puede
automáticamente decidir si una cadena (palabra) pertenece o no al lenguaje denotado por la expresión
regular.
Cadena Una cadena (o algunas veces palabra) es una secuencia finita de símbolos escogidos de un
alfabeto. Por ejemplo: aba es una cadena del alfabeto Σ = {a, b}
Lacadena vacia. Es la cadena de cero ocurrencias de símbolos, es denotado por ǫ.
Longitud de una cadena. Es el número de símbolos (posiciones) de una cadena. Por ejemplo aba tiene
longitud 3. La notación para la longitud de una cadena w es |w|. Y |ǫ| = 0 (la única cadena cuya
longitud es cero).
La estrella de Kleene (o la clausura de Kleene). De un lenguaje L se denota por L∗ . Es la unión
infinita∪i≥0 Li , donde L0 = {ǫ}, L1 = L y Li , para i > 1 es LLL · · · L, la concatenación de i copias de L.
Expresión regular. Se puede describir una expresión regular recursivamente como sigue:
Las constantes ǫ (cadena vacia) y ∅ (conjunto vacio) son expresiones regulares.
Si a ∈ Σ, es un símbolo, entonces a es una expresión regular.
Inducción: Si r y s son expresiones regulares entonces:
r|s es unaexpresión regular, denota la unión de los lenguajes que representan dichas expresiones regulares.
rs es una expresión regular, denota la concatenación.

r ∗ es una expresión regular, denota la estrella de kleene.
(r) es una expresión regular, denota el mismo lenguaje r.

Nota: Debido a que en algunos casos el operador “|” (unión) no está muy accesible en el teclado del
computador, enalgunas aplicaciones como el JFLAP se utiliza el + y algunos autores lo utilizan
Precedencia: Para evitar el uso exagerado de paréntesis se puede emplear la precedencia de operadores.
1. Operador unario “∗”: Tiene la mayor precedencia y es asociativo por la izquierda, es decir, se
aplica sólo a la secuencia más corta de símbolos a su izquierda que constituye una expresión
regular.
2. Laconcatenación, o “punto”: tiene la segunda mayor precedencia y es asociativo por la izquierda. Este operador se representa con un punto, pero por fines prácticos se obvia, en su lugar se
ubican los símbolos

Oliver A. Vilca H.

Pág. 2

dor

3. La unión “|”: tiene la menor precedencia y es asociativo por la izquierda.
En ocasiones no se desea que una expresión regular sea agrupada según laprecedencia de los operadores. En dicho caso, se puede emplear paréntesis para agrupar los operandos de la forma que se
requiera. por conveniencia.

Ejemplos:

Complete los espacios en blanco.

Lenguaje regular
{a, b}
{ǫ, b}
{a, ab}
{abe, ace, _____}

Bor
ra

{a, b, c, d}
{ǫ, b, bb, bbb, bbbb, ...}
{a, ab, abb, abbb, abbbb, ...}

Expresión regular
a|b
ǫ|b
a|ab = a(ǫ|b)
a(b|c|d)e...