Expresiones Regulares

Las expresiones regulares son usadas para definir patrones, los cuales pueden encontrarse en cadenas o palabras de algún lenguaje, pero no estan restringidas solo a este contexto, pueden ser también cualquier patrón que tenga cierta recurrencia en cualquier otro contexto. Son utilizadas en muchas de las herramientas para análisis léxico, donde se trabaja directamente con cadenas de texto para encontrar los patrones que existen en el lenguaje.
Las expresiones regulares se clasifican de la siguiente manera:
Sea $\Sigma$ un alfabeto, y $w$ una palabra, tal que $w\in \Sigma$, entonces:

• $w$ por si sola es una expresión regular. Representa el conjunto que contiene todas las cadenas de un solo símbolo.
• Si $e_1$ y $e_2$ son ambas expresiones regulares, $e_1\cdot e_2$ es una expresión regular.
• Si $e_1, e_2,\ldots,e_ {n-1}, e_n$, son expresiones regulares, la unión $(e_1\cup e_2\cup\ldots\cup e_ {n-1}\cup e_n)$ resulta en una expresión regular.
• Si $e$ es una expresión regular, entonces $e^*$ también lo es.
• Las expresiones regulares son las mencionadas antes, ninguna otra expresión es regular.

Podemos simplificar la notación de un lenguaje usando las expresiones regulares ya que funcionan como una plantilla para indicar la forma que deben tener todas las cadenas que forman parte de algún lenguaje.

$$\begin{array}{lll} a\cup b&\textrm{denota el lenguaje}&\{a\... ...\{a\}^*\\ a^+&\textrm{denota el lenguaje}&\{a\}^+ \end{array}$$

Cualquier tipo de lenguaje se puede describir por medio de expresiones regulares. Existen ciertas equivalencias entre distintos tipos de máquinas de estados finitos, de las cuales se dará una descripción breve más adelante.