Введение в схемы, автоматы и алгоритмы



             

Регулярные выражения и языки - часть 2


Например, (((1?0)?((1)*+0)) можно записать как 10(1* + 0).

Определение 5.1.

Два регулярных выражения r и p называются эквивалентными, если совпадают представляемые ими языки, т.е. Lr=Lp. В этом случае пишем r = p.

Нетрудно проверить, например, такие свойства регулярных операций:

  • r + p= p+ r (коммутативность объединения),
  • (r+p) +q = r + (p+q) (ассоциативность объединения),
  • (r p) q = r (p q) (ассоциативность конкатенации),
  • (r*)* = r* (идемпотентность итерации),
  • (r +p) q = rq + pq (дистрибутивность).

Пример 5.1.

Докажем в качестве примера не столь очевидное равенство: (r + p)* = (r*p*)*.

Пусть L1 - язык, представляемый его левой частью, а L2 - правой. Пустое слово ? принадлежит обоим языкам. Если непустое слово w

L1, то по определению итерации оно представимо как конкатенация подслов, принадлежащих языку Lr
Lp. Но этот язык является подмножеством языка L'=Lr*Lp* (почему?). Поэтому w
L2 = (L')*. Обратно, если слово w
L2, то оно представимо как конкатенация подслов, принадлежащих языку L'. Каждое из таких подслов v представимо в виде v= v11… vk1 v12… vl2, где для всех i=1, … , k подслово vi1
Lr и для всех j=1, … , l подслово vj2
Lp (возможно, что k или l равно 0). Но это значит, что w является конкатенацией подслов, каждое из которых принадлежит Lr
Lp и, следовательно, w
L1.

Рассмотрим несколько примеров регулярных выражений и представляемых ими языков.

Пример 5.2. Регулярное выражение (0 +1)* представляет множество всех слов в алфавите {0, 1}.

Пример 5.3. Регулярное выражение 11(0 +1)*001 представляет язык, состоящий из всех слов в алфавите {0, 1}, которые начинаются на '11', а заканчиваются на '001'.

Пример 5.4. Регулярное выражение (1 +01 +001)*(? + 0 +00) представляет язык, состоящий из всех слов в алфавите {0, 1}, которые не содержат подслово '000' ( см. задачу 5.3).

Пример 5.5. Регулярное выражение 1*(01*01*)* представляет язык L0ч, состоящий из всех слов в алфавите {0, 1}, в которых четное число нулей.

Действительно, каждое слово из L0ч либо вообще не содержит нулей, т.е.


Содержание  Назад  Вперед