Wyrażenia regularne

ZA Regular Expression można zdefiniować rekurencyjnie w następujący sposób -

• ε jest wyrażeniem regularnym wskazuje język zawierający pusty ciąg. (L (ε) = {ε})

• φ jest wyrażeniem regularnym oznaczającym pusty język. (L (φ) = { })

• x jest wyrażeniem regularnym, gdzie L = {x}

• Jeśli X jest wyrażeniem regularnym oznaczającym język L(X) i Y jest wyrażeniem regularnym oznaczającym język L(Y), następnie

  • X + Y jest wyrażeniem regularnym odpowiadającym językowi L(X) ∪ L(Y) gdzie L(X+Y) = L(X) ∪ L(Y).

  • X . Y jest wyrażeniem regularnym odpowiadającym językowi L(X) . L(Y) gdzie L(X.Y) = L(X) . L(Y)

  • R* jest wyrażeniem regularnym odpowiadającym językowi L(R*)gdzie L(R*) = (L(R))*

• Jeśli zastosujemy którąś z reguł kilka razy od 1 do 5, są to wyrażenia regularne.

Niektóre przykłady RE

Wyrażenia regularne	Regularny zestaw
(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) *	Zbiór ciągów a i b o dowolnej długości, w tym ciąg pusty. Więc L = {ε, a, b, aa, ab, bb, ba, aaa …….}
(a + b) * abb	Zbiór ciągów a i b zakończonych napisem abb. Więc L = {abb, aabb, babb, aaabb, ababb, ………… ..}
(11) *	Zbiór składający się z parzystej liczby jedynek, w tym pusty ciąg, więc L = {ε, 11, 1111, 111111, ……….}
(aa) * (bb) * b	Zbiór ciągów składający się z parzystej liczby a, po której następuje nieparzysta liczba b, więc L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..}
(aa + ab + ba + bb) *	Ciąg a i b o parzystej długości można uzyskać, łącząc dowolną kombinację ciągów aa, ab, ba i bb, w tym null, więc L = {aa, ab, ba, bb, aaab, aaba, ………… .. }