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

Question

Я изучаю регулярные выражения, читая книгу Ахо. Я не понимаю два утверждения в книге:

Вопрос A:

1(0+1)*1 + 1 : denotes the set of all strings beginning and ending with a 1.

Мой вопрос, почему в конец регулярного выражения добавляется +1? Разве 1(0+1)*1 не должно быть достаточно?

---

У меня также возникают проблемы со следующим:

Вопрос B:

Набор строк, содержащих только 0 и 1, которые имеют не более одного 1, как показано ниже

    0*+0*10* 

Можете ли вы объяснить, как решение 0*+0*10* приходит, шаг за шагом?

Answer 1

Что касается вопроса a: 1 (0 + 1) * 1 не совпадает с односимвольной строкой 1, которая начинается и заканчивается 1. Для этого нужен особый случай, как в примере.

Что касается вопроса b: я не могу говорить за автора.Однако ... Любая строка, которая содержит не более одного 1, является строкой, которая либо не имеет 1, либо имеет ровно 1 1. Предполагая, что алфавит равен {0,1}, первая означает любую строку, которая содержит ноль или более 0, чтоесть, 0 *.Последнее, с тем же допущением, означает любую строку, которая содержит ноль или более 0, за которыми следует один 1, за которым следует ноль или mpre 0, то есть 0 * 10 *.Сочетание этих результатов дает пример.

Answer 2

Для вопроса a : 1(0+1)*1 обозначает набор всех строк, начинающихся и заканчивающихся одной, но не содержащих строку 1, которая имеет длину одну и начинается и заканчивается одной.

Для вопроса b : Набор строк, содержащих не более одного 1 = A + B, где A - набор всех строк, содержащих ноль 1 s и B - это набор всех строк, содержащих ровно одну 1

То есть А 0*, а Б 0*10* Следовательно мы получаем ответ как 0* + 0*10*

Answer 3

В первом примере строка, принятая + 1, но не остальная, - 1.Остальные выражения могут обрабатывать 11, но не строку, где первый и последний символы одинаковы.

Это аналогично для второй строки - 0 * обрабатывает строки всех нулей, 0 * 10 * обрабатываетстроки 1 единица.