Síntaxis y semántica

Sea $\Sigma$ un alfabeto. Una expresión regular $\alpha$ sobre $\Sigma$ se define con las siguientes reglas (inductivas):

1. 1. $\emptyset$ es una expresión regular
   2. $\epsilon$ es una expresión regular
   3. si $\sigma\in\Sigma$, entonces $\sigma$ es una expresión regular
2. si $\alpha$ y $\beta$ son expresiones regulares, entonces también
   1. $\alpha.\beta$ es una expresión regular (obviamos del punto muchas veces)
   2. $(\alpha+\beta)$ es una expresión regular
3. si $\alpha$ es una expresión regular, entonces también
   1. $(\alpha)$ es una expresión regular
   2. $(\alpha)^*$ es una expresión regular

Como observamos: hemos introducido meta-símbolos (`$($',`$)$',`${}^*$',`$+$',`$.$',`$\emptyset$'). Si alguno de ellos aparece en $\Sigma$ tenemos un problema (Houston) que resolveremos al final de esta sección.

Ejemplos:

Sea $\Sigma=\{a,b,c\}$. Posibles expresiones regulares son:

$$((a.b)^*+b.c.(a)^*)\qquad ((a.a.a+b.c)+(c.b)^*.(b)^*)$$

Con eso hemos definido una síntaxis de expresiones regulares, pero ¿cuál será su semántica?

Para cada expresión regular definimos un lenguaje correspondiente (basado en las reglas).

El lenguaje $L(\alpha)$ definido por una expresión regular $\alpha$ se define:

1. 1. $L(\emptyset)=\emptyset$
   2. $L(\epsilon)=\{\epsilon\}$
   3. si $\sigma\in\Sigma$, entonces $L(\sigma)=\{\sigma\}$
2. si $\alpha$ y $\beta$ son expresiones regulares, entonces
   1. $L(\alpha.\beta)=L(\alpha).L(\beta)$
   2. $L((\alpha+\beta))=L(\alpha)\cup L(\beta)$
3. si $\alpha$ es una expresión regular
   1. $L((\alpha))=L(\alpha)$
   2. $L((\alpha)^*)=(L(\alpha))^*$

Ejemplos: sobre $\Sigma=\{0,1\}$:

• el lenguaje que contiene una subcadena 11:

  
  

  $$((0+1))^*.1.1.((0+1))^*$$
  
  

• todas las cadenas que alternan 0 y 1:

  
  

  $$(((0.1)^*+(0.1)^*.0)+((1.0)^*+(1.0)^*.1))$$
  
  

  o también con la expresión

  
  

  $$(1+\epsilon).(0.1)^*.(0+\epsilon)$$