SSL: expresiones regulares 1

La forma más precisa y más útil de representar a los Lenguajes Regulares es mediante las llamadas expresiones regulares. Estas expresiones se construyen utilizando los caracteres del alfabeto sobre el cual se define el lenguaje, el símbolo ε (que representa la ausencia de cualquier carácter), ciertos operadores especiales que veremos a continuación, y, eventualmente, haciendo uso de paréntesis para modificar las prioridades de los operadores, tal como ocurre también con las expresiones aritméticas.

Expresiones regulares para lenguajes regulares finitos

Una EXPRESIÓN REGULAR para un LR finito se obtiene mediante la utilización de caracteres del alfabeto, el símbolo ε, y los operadores: concatenación (•), que ordena la ubicación de ciertos caracteres, y unión (+), también llamado operador “ó”, que representa una elección entre caracteres o grupos de caracteres.

El operador “concatenación” tiene mayor prioridad que el operador “unión”.

Ejemplo 1

La Expresión Regular a representa al Lenguaje Regular que contiene solamente la palabra a, es decir: L = {a}.

** Observe que, ahora, un carácter puede representar un símbolo de un alfabeto, una palabra de longitud 1 o una Expresión Regular. El contexto determina a qué se refiere ese carácter en una situación determinada.

Ejemplo 2

La Expresión Regular ε representa al Lenguaje Regular que solo contiene la palabra vacía:  L = {ε}.

Ejemplo 3

La Expresión Regular a•b (habitualmente se escribe ab y se lee “a concatenado con b” o, simplemente, “ab”) representa el LR de una sola palabra, L = {ab}.

** Recuerde que, en general, la concatenación no es conmutativa; por ello, se puede hablar de “concatenación a izquierda” y de “concatenación a derecha”.

Ejemplo 4

Por lo enfatizado anteriormente, las Expresiones Regulares ab y ba representan dos lenguajes distintos. En la primera ER, el símbolo b está “concatenado a derecha”, mientras que en la segunda ER el carácter b está “concatenado a izquierda”.