Разметка регулярных выражений

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

1. Индекс места перед итерационными скобками распространяется на место, непосредственно следующее за этими скобками.

2. Индекс конечного места любого дизъюнктивного члена, заключенного в итерационные скобки, распространяется на начальные места всех дизъюнктивных членов, заключенных в эти итерационные скобки.

3. Индекс места перед итерационными скобками распространяется на место, непосредственно следующее за этими скобками.

4. Индекс конечного места любого дизъюнктивного члена, заключенного в итерационные скобки, распространяется на начальные места всех дизъюнктивных членов, заключенных в эти итерационные скобки.

5. Индексы мест, слева и справа от которых стоят буквы, никуда не распространяются.

6. В автоматах многократного действия индекс конечного места всего выражения распространяется на те же места, на которые распространяется индекс начального места. Это правило справедливо только в тех случаях, когда событие представлено регулярным выражением так, что оно не содержит многократно повторяющихся слов, входящих в заданное событие. И тогда организация автомата многократного действия осуществляется путем разметки.

Смысл приведенных правил подчинения мест сводится к следующему: основному месту с индексом i подчиняется место j, если автомат, находящийся в состоянии i, может принять букву входного алфавита, записанную непосредственно справа от места j. Рассмотрим эти правила на примере синтеза автомата, описываемого следующим регулярным выражением:

В этом автомате сигнал y ₁ выдается после поступления подряд 3-х букв x ₁, а y ₂ – после x ₂, следующей за серией из 3-х и более букв x ₁. В остальных случаях выдается буква e.

Индексы основных мест записываются непосредственно под регулярными выражениями, а индексы предосновных мест располагаются ниже индексов основных мест, под горизонтальной чертой. Выражение имеет 12 основных мест (от 0 до 11).

Проведем разметку предосновных мест. В начале определим, какие буквы может принять автомат, если он находится в состоянии 0. Поскольку на вход автомата может поступить любое из трех слов, записанных в итерационных скобках, то индекс 0 распространяется на каждое из трех предосновных мест, расположенных в начале этих слов. Учитывая, что событие, соответствующее выражению, записанному в итерационных скобках, содержит пустое слово е, индекс 0 распространяется на предосновное место, расположенное сразу за скобками. Это означает, что в частном случае ни одно из трех слов, заключенных в итерационные скобки, на вход автомата не поступит и тогда первой буквой, которую принимает автомат, является буква x ₁, стоящая непосредственно за итерационными скобками. Таким образом, все эти предосновные места подчинены месту с индексом 0.

Теперь найдем предосновные места, на которые распространяется индекс 1. Если автомат находится в состоянии 1, то он может принять букву x ₂, расположенную слева от места 1, так как эта буква находится в итерационных скобках и, следовательно, неоднократно может повторяться во входном слове автомата. Кроме того, в состоянии 1 автомат может принять начальные буквы других слов, расположенных в итерационных скобках, и букву x ₁, непосредственно следующую за этими скобками. Таким образом, месту с индексом 1 в данном случае подчиняются те же предосновные места, что и месту с индексом 0. Если автомат находится в состоянии 2, то он может принять только букву x ₂, расположенную справа от места с индексом 2. Поэтому индекс распространяется на единственное предосновное место, являющееся одновременно основным местом 2. Аналогично можно найти подчиненные места других основных мест.

По окончании слова, входящего в событие S, автомат переходит в состояние 11, после чего на вход автомата может поступить второе слово этого события S, так как мы считаем, что автомат является автоматом многократного действия. Автоматами многократного действия называются такие автоматы, которые могут неоднократно принимать слова, входящие в события, представленные в автомате. В таких автоматах индекс конечного места распространяется на те же предосновные места, на которые распространяется индекс начального места, т.е. по окончании очередного слова на вход автомата этого слова может поступить вновь.

По размеченному регулярному выражению теперь можно составить таблицу переходов автомата. Однако перед построением таблицы целесообразно уменьшить число индексов основных мест, а следовательно и число внутренних состояний автомата.

Вопросы к лекции 13:

1. Что используют для задания конечного автомата?

2. Дать определение дизъюнкции событий?

3. Дать определение произведению событий?

4. Дать определение итерации события?

5. Из каких этапов состоит абстрактный синтез?

6. Общие правила подчинения мест регулярного выражения?

7. Расскажите об алгоритме синтеза автомата Мура?

8. Дать определение регулярного события и регулярного выражения?

ЛЕКЦИЯ 14

Поиск по сайту: