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



             

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


входит в язык, представляющий 1*, либо может быть разбито на блоки вида 01i01j, i,j
0, которым, быть может, предшествует блок единиц. Выражение (01*01*), очевидно задает один такой блок, а его итерация - произвольную последовательность таких блоков.

Пример 5.6. Построим теперь регулярное выражение, представляющее язык L0ч1ч, который состоит из всех слов в алфавите {0, 1}, содержащих четное число нулей и четное число единиц.

Пусть w=w1w2 … wn - произвольное слово из L0ч1ч. Тогда, разумеется, n - четно, пусть n=2k. Разобьем w на пары соседних букв pi =w2i-1w2i, i= 1,2,… ,k. Возможны 4 вида таких пар: 00, 11, 01 и 10. Пар вида 00 и 11 может быть сколько угодно, а пар вида 01 и 10 обязательно четное число. Поэтому w разбивается на блоки, каждый из которых начинается одной из пар 01 или 10 и содержит еще одну такую пару. Каждый такой блок описывается выражением (01 +10)(00 + 11)*(01+10)(00 + 11)*. При этом перед первым блоком может быть префикс, состоящий из пар 00 и 11. Множество слов состоящих из пар 00 и 11 задается выражением (00 +11)*. Отсюда получаем выражение R0ч1ч, задающее язык L0ч1ч:

R_{0\textit{ч}1\textit{ч} }= (00 +11)^*((01 +10)(00 + 11)^*(01+10)(00 + 11)^*)^*




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