АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Алгоритм синтеза автомата Мура

Читайте также:
  1. II. Методы непрямого остеосинтеза.
  2. IV. Современные методы синтеза неорганических материалов с заданной структурой
  3. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  4. А) Закон диалектического синтеза
  5. Алгоритм
  6. Алгоритм 65 «Кровотечение в послеродовом периоде»
  7. Алгоритм 72 «Ожоги и травмы глаза, века, конъюнктивы»
  8. Алгоритм MD4
  9. Алгоритм RC6
  10. Алгоритм RSA
  11. Алгоритм Брезенхема для окружности
  12. Алгоритм Брезенхема.

Рассмотрим пример абстрактного синтеза автомата для случая, когда регулярные отношения составлены без применения операции итерации. Составим отмеченную таблицу переходов автомата, имеющего входной алфавит 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. Затем каждое предосновное место отмечается совокупностью индексов основных мест. В эту совокупность входят индексы внутренних состояний, находясь в которых автомат может принять букву, стоящую справа от предосновного места.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 |

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

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)