Expresiones Regulares

Sea $V$ un alfabeto finito, una expresión regular en $V$ es un string finito compuesto por símbolos del conjunto $\{q\in Q/\lambda [q]\cap F\ne \varphi \}$ y se forma de acuerdo a:

• $\lambda$ es una expresión regular.
• $\varphi$ es una expresión regular,
• Si $a\in V$, $a$ es una expresión regular.

Si $\alpha$ y $\beta$ son expresiones regulares, también lo son $(\alpha \beta )$, $\alpha \cup \beta )$, y $({\alpha }^{\ast })$.

Por ejemplo, una expresión regular $(0\cup 1{)}^{\ast }$ describe el conjunto regular $\{\{0\}\cup \{1\}{\}}^{\ast }$. Ese conjunto es un lenguaje regular aceptable por un Aceptor de Estado Finito.

Dos expresiones regulares son equivalentes $⟺$ describen el mismo conjunto regular.

Propiedades de las expresiones regulares:

1. $({\alpha }^{\ast }{)}^{\ast }={\alpha }^{\ast }$
2. ${\alpha }^{\ast }{\alpha }^{\ast }={\alpha }^{\ast }$
3. $(\lambda \cup \alpha {)}^{\ast }={\alpha }^{\ast }$
4. $\alpha {\alpha }^{\ast }={\alpha }^{\ast }\alpha$
5. $\alpha {\alpha }^{\ast }\cup \lambda ={\alpha }^{\ast }$
6. $\alpha (\beta \cup \gamma )=\alpha \beta \cup \alpha \gamma$
7. $\alpha (\beta \alpha {)}^{\ast }=(\alpha \beta {)}^{\ast }\alpha$
8. $(\alpha \cup \beta {)}^{\ast }=({\alpha }^{\ast }\cup {\beta }^{\ast }{)}^{\ast }$
9. $(\alpha \cup \beta {)}^{\ast }=({\alpha }^{\ast }{\beta }^{\ast }{)}^{\ast }$
10. $(\alpha \cup \beta {)}^{\ast }={\alpha }^{\ast }(\beta \alpha {)}^{\ast }=(\alpha \beta {)}^{\ast }{\alpha }^{\ast }$
11. $\lambda \cup (\alpha \cup \beta {)}^{\ast }\beta =({\alpha }^{\ast }\beta {)}^{\ast }$
12. $\lambda \cup \beta (\alpha \cup \beta {)}^{\ast }=(\beta {\alpha }^{\ast }{)}^{\ast }$
13. $\alpha =\beta \alpha \cup \gamma ⟺\alpha ={\beta }^{\ast }\gamma$ (regla de Arden)
14. $\alpha =\alpha \beta \cup \gamma ⟺\alpha =\gamma {\beta }^{\ast }$ (regla de Arden)

Dada una expresión regular $\gamma$ que describe al conjunto $X$, es posible construir una ${\gamma }^R$ que describa al conjunto $X^R$ que contiene el reverso de cada string en $X$:

1. Si $\gamma =\lambda$, $\varnothing$, $\mathbf{a}$ con $a\in V$ $⟹{\gamma }^R=\gamma$
2. Si $\gamma =(\alpha \beta )$ $⟹{\gamma }^R={\beta }^R{\alpha }^R$
3. Si $\gamma =(\alpha \cup \beta )$ $⟹{\gamma }^R={\alpha }^R\cup {\beta }^R$
4. Si $\gamma ={\alpha }^{\ast }$ $⟹{\gamma }^R={\alpha }^{R\ast }$

Construcción de AEF a partir de Expresiones Regulares

Teorema

Dada la expresión regular $\gamma$ sobre el alfabeto finito $V$, se puede construir un AEF-$\lambda$ $M/L(M)=\gamma$.

Método 1 de construcción: