Expressões regulares

UMA Regular Expression pode ser definido recursivamente da seguinte forma -

• ε é uma expressão regular indica o idioma que contém uma string vazia. (L (ε) = {ε})

• φ é uma expressão regular que denota um idioma vazio. (L (φ) = { })

• x é uma expressão regular onde L = {x}

• E se X é uma expressão regular que denota o idioma L(X) e Y é uma expressão regular que denota o idioma L(Y), então

  • X + Y é uma expressão regular correspondente ao idioma L(X) ∪ L(Y) Onde L(X+Y) = L(X) ∪ L(Y).

  • X . Y é uma expressão regular correspondente ao idioma L(X) . L(Y) Onde L(X.Y) = L(X) . L(Y)

  • R* é uma expressão regular correspondente ao idioma L(R*)Onde L(R*) = (L(R))*

• Se aplicarmos qualquer uma das regras várias vezes de 1 a 5, elas serão expressões regulares.

Alguns exemplos de RE

Expressões 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 strings de a's eb's de qualquer comprimento, incluindo a string nula. Então L = {ε, a, b, aa, ab, bb, ba, aaa …….}
(a + b) * abb	Conjunto de strings de a's eb's terminando com a string abb. Portanto, L = {abb, aabb, babb, aaabb, ababb, ………… ..}
(11) *	Conjunto consistindo em número par de 1's incluindo string vazia, So L = {ε, 11, 1111, 111111, ……….}
(aa) * (bb) * b	Conjunto de strings que consiste em um número par de a's seguido por um número ímpar de b's, então L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..}
(aa + ab + ba + bb) *	Sequências de a's eb's de comprimento par podem ser obtidas concatenando qualquer combinação das strings aa, ab, ba e bb incluindo null, então L = {aa, ab, ba, bb, aaab, aaba, ………… .. }