Expresiones regulares

UNA Regular Expression se puede definir recursivamente de la siguiente manera:

  • ε es una expresión regular indica el idioma que contiene una cadena vacía. (L (ε) = {ε})

  • φ es una expresión regular que denota un lenguaje vacío. (L (φ) = { })

  • x es una expresión regular donde L = {x}

  • Si X es una expresión regular que denota el idioma L(X) y Y es una expresión regular que denota el idioma L(Y), luego

    • X + Y es una expresión regular correspondiente al idioma L(X) ∪ L(Y) dónde L(X+Y) = L(X) ∪ L(Y).

    • X . Y es una expresión regular correspondiente al idioma L(X) . L(Y) dónde L(X.Y) = L(X) . L(Y)

    • R* es una expresión regular correspondiente al idioma L(R*)dónde L(R*) = (L(R))*

  • Si aplicamos alguna de las reglas varias veces del 1 al 5, son Expresiones Regulares.

Algunos ejemplos de RE

Expresiones regulares Conjunto regular
(0 + 10 *) L = {0, 1, 10, 100, 1000, 10000,…}
(0 * 10 *) L = {1, 01, 10, 010, 0010,…}
(0 + ε) (1 + ε) L = {ε, 0, 1, 01}
(a + b) * Conjunto de cadenas de a y b de cualquier longitud, incluida la cadena nula. Entonces L = {ε, a, b, aa, ab, bb, ba, aaa …….}
(a + b) * abb Conjunto de cadenas de a y b que terminan con la cadena abb. Entonces L = {abb, aabb, babb, aaabb, ababb, ………… ..}
(11) * Conjunto formado por un número par de unos, incluida una cadena vacía, de modo que L = {ε, 11, 1111, 111111, ……….}
(aa) * (bb) * b Conjunto de cadenas que consta de un número par de a seguido de un número impar de b, por lo que L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..}
(aa + ab + ba + bb) * Se puede obtener una cadena de a y b de longitud uniforme concatenando cualquier combinación de las cadenas aa, ab, ba y bb incluyendo nulo, por lo que L = {aa, ab, ba, bb, aaab, aaba, ………… .. }