Синтез цифровых автоматов. Захаров Н.Г - 42 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

41
выражении R являются буквы алфавита Х, символ пустого слова ε, знак дизъюнкции,
итерационные и обычные скобки).
Кроме этих так называемых разделяющих мест (знаков раздела) вводится
еще два места – начальное и конечное. Первое их них располагается слева от самого
левого знака выражения R, а второе – справа от самого правого знака.
Например, R = z ∨ x {y ∨ z}, где R – регулярное выражение.
Приведем это выражение к правильной форме
R = (z ∨ x {y ∨ z}).
Проведем разметку
| ( | z | ∨ | x | { | y | ∨ | z | } | ) | (1)
1 2 3 4 5 6 7 8 9 10 11 .
Из выражения (1) видно, что регулярное выражение R имеет 11 мест.
Развернем данное регулярное выражение в слово, т. е. последовательно, буква
за буквой, выпишем какое-либо слово из представляемого им события. При этом раз-
вертывание, будем осуществлять переходя от одного места данного регулярного вы-
ражения к другому и от начального места к конечному месту. Такие переходы быва-
ют двух видов – непосредственный переход и переход через букву основного алфа-
вита Х, в котором задается представляемое выражением событие.
В качестве примера рассмотрим процессы развертывания размеченного выше
выражения R в принадлежащие представляемому им событию слова z и xyz.
При развертывании выражения в первое слово необходимо осуществить непо-
средственный переход от начального места 1 к месту 2, переход через букву z от мес-
та 2 к месту 3 и непосредственный переход от 3 к конечному месту 11.
При развертывании выражения в слово xyz порядок переходов будет следую-
щий: непосредственный переход от места 1 к месту 4 переход через букву x – от 4 к
5, непосредственный переход – от 5 к 6, переход через букву у – от 6 к 7, непосредст-
венный переход от 7 к 10, непосредственный переход от 10 к 8, переход через букву
z – от 8 к 9, непосредственный переход от 9 к 10 и непосредственный переход от 10 к 11.
Пусть R – регулярное выражение, q = x
i1
x
i2
…x
ik
произвольное слово во вход-
ном алфавите события, представляемого выражением R.
Условимся, что место α в выражении R связано словом q с местом β в том
же выражении, если от места α к месту β можно перейти с помощью чередования
любого числа непосредственных переходов и переходов через буквы x
i1
, x
i2
, …, x
ik
слова q, взятых по одному разу в том порядке, в каком они входят в слово. Это усло-
вие означает, что место β q–следует за местом α всякий раз, когда α связано с ме-
стом β словом q.
Также условимся говорить, что место β подчинено месту
α
, если от места α к
месту β можно перейти с помощью одних лишь непосредственных переходов, т. е.
если место α связано с местом β пустым словом ε.
Правила подчинения мест в регулярных выражениях
1. Начальные места всех термов многочлена, помещенного в обычные или ите-
рационные скобки, подчинены месту, находящемуся непосредственно слева от от-
крывающей скобки из пары скобок, в которые заключен данный многочлен (много-
член по этому правилу может вырождаться в одночлен с обязательным заключением
его в скобки).

Страницы