Пример.

 

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

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. Рассмотрим запись выражений в этой системе и затем – два важных класса приложений, основанных на регулярных выражениях: лексические анализаторы и поиск в тексте.