Siguiente: Interpretación estándar Un nivel arriba: Presentación formal Anterior: Presentación formal

Sintaxis de las expresiones regulares

Sea $\Sigma$ un alfabeto. La clase de expresiones regulares sobre $\Sigma$, $\mbox{\it ER\/}(\Sigma)$, se define recursivamente:

$$\begin{eqnarray*}& & \mbox{\bf0},\mbox{\bf 1}\in\mbox{\it ER\/}(\Sigma) \\ s\i... ...x{\it ER\/}(\Sigma)&\Rightarrow& K^*\in\mbox{\it ER\/}(\Sigma) \end{eqnarray*}$$

Las expresiones regulares que poseen la CPV (condición de la palabra vacía) se determinan también recursivamente:

$$\begin{eqnarray*}K=\mbox{\bf 1} &\Rightarrow& K\in\mbox{\it CPV\/}(\Sigma) \\ ... ...{\it CPV\/}(\Sigma) &\Rightarrow& K\in\mbox{\it CPV\/}(\Sigma) % \end{eqnarray*}$$

Identificaremos entre sí a las expresiones regulares de acuerdo con las igualdades formuladas en las proposiciones 4.1.1 y 4.1.2. En otras palabras, si K,L,M son expresiones regulares entonces supondremos válidos los axiomas enlistados en la tabla (4.1).

  

Table 4.1: Axiomas de las expresiones regulares.

y, por supuesto, éstos implican una a una todas las ecuaciones (4.1-4.14). Ahora bien las ecuaciones vistas de las expresiones regulares son propiamente reglas de transformación: Si una expresión regular coincide con uno de los miembros en uno de los miembros de esas ecuaciones entonces se puede transformar en el otro miembro. Dos expresiones son entonces equivalentes si una se puede llevar a la otra mediante la aplicación de un número finito de esas reglas de transformación. En particular, si se buscase expresiones equivalentes con el menor número de operadores, dándole prioridad a las acciones ``más a la derecha'', de entre las ecuaciones (4.1-4.14) se podría escoger las ``producciones'' enlistadas en la tabla (4.2).

  

Table 4.2: Reglas de producción para reducir expresiones regulares.

Ejemplo. Sobre el alfabeto $\mbox{\it Dos\/}=(0+1)$, consideremos la expresión regular:

$$\mbox{\it exp\/}_1=1^* + (1^* + 1^* 0^*) (1^* + 1^* 0^*)^* 1^*$$

Las producciones anteriores realizan la transformación siguiente:

$$\begin{array}{rclclcl} \mbox{\it exp\/}_1 &=& \left[\mbox{\b... ...)^* \\ &=& \left(0^* + 1 \right)^* &\ &\ &\ &\ % \end{array}$$

y sirva el ejemplo para ilustrar que el símbolo $\mbox{\bf 1}$ que denota a la palabra vacía es distinto del símbolo $1\in\mbox{\it Dos\/}$.


Como un segundo ejemplo, de manera inductiva en la caracterización de las expresiones con la CPV se demuestra la siguiente:

Observación 2.1   Para toda expresión regular K que posea la CPV existe una expresión regular L tal que L no posee la CPV y $K=\mbox{\bf 1}+L$.

Siguiente: Interpretación estándar Un nivel arriba: Presentación formal Anterior: Presentación formal