Какие типы строк генерируются (a*+b*)

Если вы не работаете с языком регулярных выражений, который явно классифицирует *+ как специальный токен, который либо имеет особое значение, либо зарезервирован для будущего расширения (и создает определенное поведение сейчас или синтаксическую ошибку), естественный анализ a*+ что это означает (a*)+: постфикс + применяется к выражению a*.

Если эта интерпретация применима, далее мы можем заметить, что (a*)+ эквивалентно просто a*. Следовательно, a*+b* совпадает с a*b*.

Во-первых, по определению R+ означает RR*. Сопоставьте один R, а затем ноль или более из них. Следовательно, мы можем переписать (a*)+ как (a*)(a*)*.

Во-вторых, * идемпотентно, поэтому (a*)* это просто (a*). Если мы сопоставим «ноль или более a», ноль или более раз, ничего не изменится; чистый эффект равен нулю или более a. Доказательство: R* обозначает это бесконечное расширение: (|R|RR|RRR|RRRR|RRRRR|...): ничего не соответствует, или соответствует одному R, или соответствует двум R, ... Следовательно, (a*)* dentes это расширение: (|a*|a*a*|a*a*a*|...). Эти внутренние a*, в свою очередь, обозначают отдельные расширения второго уровня: (|(|a|aa|aaa|...|)|(|a|aa|aaa|...)(a|a|aaa|...))|...). Благодаря ассоциативному свойству ветви | мы можем сгладить структуру, подобную (a|(b|c)), в (a|b|c), и когда мы проделаем это с расширением, мы заметим, что существует множество идентичных терминов: пустое регулярное выражение (), одиночное a, двойное aa и т. д. . Все они сводятся к одной копии, потому что (|||) эквивалентно (), а (a|a|a|a|...) эквивалентно только (a) и так далее. То есть, когда мы сортируем термины по возрастанию длины и сжимаем несколько идентичных терминов в одну копию, мы получаем (|a|aa|aaa|aaaa|...), что распознается как расширение всего лишь a*. Таким образом, (a*)* есть a*.

Наконец, (a*)(a*) означает просто a*. Доказательство. Как и в предыдущем случае, мы расширяемся на ветки: (|a|aa|aaa|...)(|a|aa|aaa|...). Далее мы отмечаем, что цепочка выражений ветвления эквивалентна набору термов в декартовом произведении. То есть (a|b|c|..)(i|j|k|...) означает именно: (ai|aj|ik|...|bi|bj|bk|...|ci|cj|ck|...|...). Когда мы применяем этот продукт к (|a|aa|aaa|...)(|a|aa|aaa|...), мы получаем множество терминов, которые, если их упорядочить по возрастающей длине и подвергнуть дедупликации, сокращаются до (|a|aa|aaa|aaaa|...), а это всего лишь a*.

Я думаю, что здесь полезно взглянуть на формальное определение регулярных выражений, т. е. найти каждое регулярное выражение, e какой язык L(e) его создает.

Итак, начнем с простого:

(1) Как насчет регулярного выражения a (только буква)? Его язык

 L(a) := {a},

просто одно слово/символ "а".

(2) Для регулярного выражения e1 + e2, где e1 и e2 сами являются регулярными выражениями,

L(e1 + e2) := L(e1) U L(e2).

Так, например. если a и b символы, L(a+b) = {a, b}.

(3) Для регулярного выражения e1 e2 (объединение), где e1 и e2 сами являются регулярными выражениями,

L(e1 e2) := all words w such that 
we can write w = w_1w_2 with w_1 in L(e1) and w_2 in L(e2)".

(4) Как насчет регулярного выражения *e**, где e может быть самим регулярным выражением? Интуитивно слово находится в L(e*), если оно имеет форму w_1 w_2w_3w_4...w_n, где w_i находится в L(e) для каждого i. Так

L(e*) := all words w such that we can write 
         w = w_1 w_2 .. w_n 
           for a n >= 0 with all w_i in L(e) (for i = 1, 2, ..., n)

Итак, как насчет L((a* + b*))?

L((a* + b*)) 
(according to rule 2)
= L(a*) U L(b*)
(according to rule 4/1)
= {eps, a, aa, aaa, aaaa, ....} U {eps, b, bb, bbb, bbbb}
= all strings that have either only a's OR only b's in it 
  (including eps, the so-called empty word)

Аналогично для (a* b*):

 L((a* b*))
 (according to rule 3)
 = all words w = w_1 w_2 with w_1 in L(a*) and w_2 in L(b*)
 = {eps eps, eps b, a eps, ab, aa eps, aab, ...}
 = {eps, b, a, ab, aa, aab, aabb, ... }
 = all strings that first have zero or more a's, then zero or more b's.

Для начала, я думаю, будет полезно «деконструировать» регулярное выражение, как мы сделали выше, поскольку регулярные выражения также можно рассматривать как деревья, как и более известные арифметические выражения, например:

    +
  /   \
 *     *
 |     |
 a     b