Siguiente: De expresiones regulares a Un nivel arriba: Presentación formal Anterior: Sintaxis de las expresiones

Interpretación estándar

Toda expresión regular se interpreta como un lenguaje:

$$\begin{eqnarray*}& & \mbox{\it Int\/}(\mbox{\bf0})=\emptyset \\ & & \mbox{\it ... ...arrow& \mbox{\it Int\/}(K^*)=\left(\mbox{\it Int\/}(K)\right)^* \end{eqnarray*}$$

Observación 2.2   Una expresión regular K posee la CPV si y sólo si $\mbox{\it nil\/}\in \mbox{\it Int\/}(K)$.

Diremos que un lenguaje $L\subset\Sigma^*$ es formalmente regular si existe una expresión regular $K\in\mbox{\it ER\/}(\Sigma)$ que se interpreta como L, es decir, K es tal que $L=\mbox{\it Int\/}(K)$. Ya que, vistos como conjuntos de palabras, los axiomas de las expresiones regulares, se cumplen en el conjunto ${\cal P}(\Sigma^*)$ se tiene, evidentemente, la

Proposición 2.1 (Coherencia)   Si dos expresiones regulares son equivalentes entonces se interpretan como un mismo lenguaje.

El recíproco también se cumple, pero su demostración excede los límites del presente curso (véase, por ej. [21]).

Proposición 2.2 (Completitud)   Si dos expresiones regulares se interpretan como un mismo lenguaje entonces son equivalentes.

El espacio cociente $\left(\mbox{\it ER\/}(\Sigma)/\equiv\right)$ se identifica naturalmente con la clase de los lenguajes formalmente regulares.