Пример

Приоритеты операторов РВ

Построение РВ

Алгебраические законы регулярных выражений

Пример

Дан язык L={0, 11}. Определить язык L^*.

L⁰={e}

L¹={0, 11}

L²={00, 011, 110, 1111}

L³={000, 0011, 0110, 1100, 01111, 11011, 11110, 111111}

…

Для вычисления L^* необходимо вычислить Lⁱ для каждого i и объединить эти языки.

Определение. Два РВ являются эквивалентными, если при подстановке любых языков вместо переменных оба выражения представляют один и тот же язык.

Алгебра РВ строится по той же схеме, что обычная арифметическая алгебра: используются константы и переменные для обозначения языков и операторы для обозначения 3 операций: объединение, конкатенация и итерация.

Базис. Состоит из 3 правил:

Индукция. Состоит из 4 правил вывода:

1. Итерация «*»

2. Конкатенация «.»

3. Объединение «+».

Например, выражение 01^*+1 группируется как (0(1^*))+1.

Напишем РВ для множества цепочек из чередующихся нулей и единиц.

1. Построим РВ для языка, состоящего из одной цепочки «01».

2. Построим выражение для всех цепочек вида 0101…01.

1. 0 и 1 – выражения для языков {0} и {1}, 01 – для языка {01}.

2. (01)^* - для всех вхождений «01».

Это еще не все, есть другие варианты правильных цепочек.

(10)^* - для всех вхождений «10».

0(10)^* - для цепочек, которые начинаются и заканчиваются нулем.

(10)^*1 - для цепочек, которые начинаются и заканчиваются единицей.

Объединяя эти цепочки получим итоговое РВ:

(01)^* + (10)^* + 0(10)^* + 1(01)^*

Задача. Построить РВ для множества цепочек из 0 и 1, в которых каждая пара смежных нулей находится перед парой смежных единиц.

1^* + (01)^* + (0011)^*

Дата добавления: 2015-05-26