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

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

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)^*

Применение регулярных выражений

Регулярные выражения широко применяются в ОС UNIX. Рассмотрим запись выражений в этой системе и затем – два важных класса приложений, основанных на регулярных выражениях: лексические анализаторы и поиск в тексте.