Блог

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

Вопрос 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* , шаг за шагом?

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

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

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

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

Итак, A — это 0* , а B — это 0*10* Следовательно, мы получаем ответ в виде 0* 0*10*

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

Аналогичное рассуждение для второй строки — 0 * обрабатывает строки со всеми нулями, 0 * 10 * обрабатывает строки из 1 единицы.