Expresiones regulares

Hasta ahora era difícil describir lenguajes aceptados por autómatas. Siempre teníamos que aprovechar de una notación como

$$L(M)=\{w \;\vert\;\mbox{ alguna propiedad de } w \}$$

Por ejemplo, si queríamos desarrollar un autómata que comprobase que una cadena codificase una dirección de correo electrónico válida tendríamos como propiedades:

1. los símbolos permitidos son: a-z, A-Z, 0-9, @ . - _
2. debe contener exactamente una @
3. por lo menos un . detrás de la @
4. detrás del último . deben venir entre 2 y 4 letras
5. detrás de cada . y de la @ debe venir por lo menos una letra
6. delante de la @ por lo menos una palabra que empieza con una letra,

es decir, $L(M)=\{w \;\vert\;w \mbox{ cumple las condiciones de arriba }\}$.

Ejercicio: ¡Intenta construir un autómata!

Sería conveniente tener un meta-lenguaje que nos permitiese describir fácilmente lenguajes (por lo menos de cierto tipo).