 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Алгоритм синтеза автомата Мура
Рассмотрим пример абстрактного синтеза автомата для случая, когда регулярные отношения составлены без применения операции итерации. Составим отмеченную таблицу переходов автомата, имеющего входной алфавит X { x 1, x 2} и реализующий следующий алгоритм:
| S 1 = x 1 x 2 v x 1 x 1 x 1, |
| S 2 = x 1 x 2 x 2 v x 2 x 2, |
| S запр. = x 1 v x 2 x 2 x 2. |
При синтезе условимся начальное состояние автомата обозначать цифрой 0, а остальные состояния – десятичными числами 1, 2, 3 и т.д. Очевидно, это самый простой, хотя и не очень экономный по числу используемых внутренних состояний автомата. Алгоритм синтеза заключается в следующем. Фиксируется начальное состояние и для входного слова, содержащего r букв, назначается r внутренних состояний. Переходы в автомате определяются так, что первая буква входного слова переводит автомат из начального состояния 0 в состояние 1, вторая буква из 1 в 2 и т.д. Аналогичные последовательности внутренних состояний назначаются для всех остальных слов. Затем все конечные состояния, в которые автомат попадает после подачи слов, входящих в событие Si, отмечаются выходными сигналами yi.
Для того, чтобы система переходов автомата была определенной, для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. Например, для регулярного события S 1 первая буква x 1 переводит автомат из начального состояния 0 в состояние 1, вторая буква x 2 – из 1 в 2:
| S 1 = | | | x 1 | | | x 2 | | | v | | | x 1 | | | x 1 | | | x 1 | | |
| S 2 = | | | x 1 | | | x 2 | | | x 2 | | | v | | | x 2 | | | x 2 | | |
| 7. |
Поскольку первая буква второго слова x 1 x 1 x 1, входящего в S 1, также есть x 1, то она переводит автомат из начального состояния 0 в 1. Вторая буква x 1 переводит автомат из 1 в 3, третья – из 3 в 4.
Первые две буквы слова x 1 x 2 x 2, входящего в S 2, совпадают с первым словом события S 1. Поэтому первые две буквы этого слова должны последовательно переводить автомат из 0 в 1, и из 1 в 2. Дальнейшие состояния обозначим числами 5, 6 и 7. Получившаяся в результате форма записи определяет разметку мест регулярных выражений.
Местами регулярного выражения называют промежутки между двумя буквами, между буквой и знаком дизъюнкции, а так же между буквой и скобкой. Кроме того, вводят начальное место, обозначаемое цифрой 0 и конечные места, отождествляемые с концом каждого слова. Для запрещенного события S запр последовательность событий можно не назначать. Для размеченных регулярных выражений составляется отмеченная таблица переходов.
| уg | е | е | y 1 | e | y 1 | y 2 | e | y 2 | e |
| x j/ai | * | ||||||||
| x 1 | * | * | * | * | * | * | |||
| x 2 | * | * | * | * | * |
Чтобы система переходов автомата была определена при подаче любого входного слова, кроме состояний 0 - 7 вводится еще одно состояние, которое обозначается звездочкой *. В это состояние автомат переходит при подаче входных слов, которые не входят в события S 1 и S 2. Выходным сигналом y 1 отмечены состояния 2 и 4, y 2 – состояния 5 и 7. Остальные состояния отмечены пустой буквой e.
Алгоритм синтеза усложняется, если регулярные выражения содержат итерационные скобки. При разметке регулярных выражений различают основные и предосновные места. Очевидно, некоторые места могут быть одновременно основными и предосновными.
Все основные места отмечаются различными десятичными числами, при этом всем начальным местам приписывается индекс 0. Затем каждое предосновное место отмечается совокупностью индексов основных мест. В эту совокупность входят индексы внутренних состояний, находясь в которых автомат может принять букву, стоящую справа от предосновного места.
Поиск по сайту: