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

А 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, ………… .. }