Регулярные выражения

А Regular Expression можно рекурсивно определить следующим образом -

• ε является регулярным выражением и указывает язык, содержащий пустую строку. (L (ε) = {ε})

• φ - это регулярное выражение, обозначающее пустой язык. (L (φ) = { })

• x это регулярное выражение, где L = {x}

• Если X регулярное выражение, обозначающее язык L(X) и Y регулярное выражение, обозначающее язык L(Y), тогда

  • X + Y это регулярное выражение, соответствующее языку L(X) ∪ L(Y) где L(X+Y) = L(X) ∪ L(Y).

  • X . Y это регулярное выражение, соответствующее языку L(X) . L(Y) где L(X.Y) = L(X) . L(Y)

  • R* это регулярное выражение, соответствующее языку L(R*)где L(R*) = (L(R))*

• Если мы применим какое-либо из правил несколько раз от 1 до 5, это будут регулярные выражения.

Некоторые примеры RE

Регулярные выражения	Обычный набор
(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 любой длины, включая пустую строку. Итак, L = {ε, a, b, aa, ab, bb, ba, aaa …….}
(а + б) * абб	Набор строк из a и b, оканчивающихся строкой abb. Итак, L = {abb, aabb, babb, aaabb, ababb, ………… ..}
(11) *	Набор, состоящий из четного числа единиц, включая пустую строку, Итак, L = {ε, 11, 1111, 111111, ……….}
(аа) * (бб) * б	Набор строк, состоящий из четного числа букв a, за которыми следует нечетное количество символов b, поэтому L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..}
(aa + ab + ba + bb) *	Строка a и b четной длины может быть получена путем конкатенации любой комбинации строк aa, ab, ba и bb, включая null, так что L = {aa, ab, ba, bb, aaab, aaba, ………… .. }