|
Второй пример абстрактного синтеза ⇐ ПредыдущаяСтр 4 из 4 Рассмотрим еще один пример абстрактного синтеза автомата. Найдем таблицу переходов автомата сравнения чисел, функционирование которого заданы следующими регулярными выражениями:
Регулярные выражения событий S 1 и S 2 содержат одинаковые сомножители в итерационных скобках, перед которыми расположено место с индексом 0. Поэтому в обоих выражениях основные места внутри итерационных скобок отмечены одинаковыми индексами (3, 4 и 5). Индекс конечного места каждого выражения распространяется на начальные места всех регулярных выражений, так как в автоматах многократного действия за словом любого события, например S 1, может быть подано слово любого другого события, то есть S 1 v S 2 v S 3. В размеченных выражениях можно объединить места с индексами 4, 6 и 5, 9:
По размеченному выражению составим отмеченную таблицу переходов:
При составлении таблицы следует учитывать, что для разных регулярных выражений автомат под действием одних и тех же входных сигналов переходит в разные состояния. Эти внутренние состояния будем отмечать множеством индексов основных мест. Например, в событии S 3 переход из состояния 0 в состояние 1 происходит под действием сигнала x r, а в S 1 под действием этого же сигнала из состояния 0 автомат переходит в состояние 3. Поэтому внутреннее состояние, в которое автомат переходит под действием xr из состояния 0, будем обозначать множеством из двух индексов 1 v 3. Аналогично получается переход из состояний 2, 7 и 9 под действием x r, а также переход из состояния 4 и 5 в состояния 3 v 6 и 3 v 8 соответственно под действием x r. При заполнении таблицы получается свободные клетки там, где переходы в автомате не определенны. Такие клетки будем отмечать звездочкой *, которую следует рассматривать как индекс некоторого внутреннего состояния. Таблица переходов составляется не только для состояний, отмеченных индексами основных мест регулярного выражения, но и для состояний, отмеченных множеством индексов. Для заполнения колонок для таких состояний достаточно образовать дизъюнкцию таких индексов, которые расположены в колонках, отмеченных индексами, входящими в множества. Например, для заполнения колонки 1v3 образуем дизъюнкцию индексов расположенных в колонках 1 и 3. Поскольку состояния 1, 3, 6 и 8 отмечены пустой буквой e, то и состояния 1v3, 3v6, 3v8 также отмечаются буквой е. После построения таблицы проведем второй этап минимизации числа внутренних состояний автомата. Можно объединить состояния, отмеченные индексами: 0 и 1v3, 4 и 3v6, 5 и 3v8. При этом состояния, отмеченные звездочкой, обозначим через 10, а состояния 1v3 – 0, 3v6 – 4, 3v8 – 5.
По построенной таблице проведем третий этап минимизации, исключив такие состояния, в которые автомат из нулевого состояния никогда перейти не может. В нашем случае такими состояниями являются 1, 3, 6, 8 и 10. Обозначив оставшиеся состояния 0 – b 0, 2 – b 1, 4 – b 2, 5 – b 3, 7 – b 4, 9 – b 5, получим окончательную таблицу переходов заданного автомата:
Четвёртый этап минимизации В некоторых случаях после получения отмеченной таблицы переходов автомата возможен четвертый этап минимизации. Правда этот этап не всегда приводит к уменьшению числа состояний и часто является проверочным. Алгоритм этого этапа рассмотрим на примере. Пусть есть автомат, заданный следующей отмеченной таблицей переходов:
Алгоритм минимизации заключается в следующем: 1. Все внутренние состояния разбиваются на группы по числу выходных сигналов. В нашем случае есть два выходных сигнала y 1 и y 2 и, следовательно, будет две группы, которые мы обозначим буквами a и b. 2. По таблице переходов автомата определяют, к каким группам принадлежат внутренние состояния, в которые автомат переходит из данного состояния под воздействием каждой буквы входного алфавита. Эти состояния запишем в виде последовательности букв под каждым из состояний автомата. Например, из состояния 0 автомат переходит в состояния 2, 3 и 1, которые принадлежат соответственно к следующим группам a, b и a. Эта последовательность букв (aba) и записывается под состоянием 0: 3. Проводят новое разделение внутренних состояний на группы, объединяя в каждой группе состояния, отмеченные одинаковой последовательностью букв. В нашем случае каждая из двух групп распадается на две группы, по числу различных последовательностей букв: 4. Пользуясь таблицей переходов автомата, вновь отмечают каждое состояние последовательностью букв. Разделение состояний на новые группы продолжают до тех пор, пока новые группы состояний появляться не будут. В нашем случае минимизация заканчивается на втором шаге, так как все состояния, входящие в группы а и с, отмечены одинаковыми последовательностями букв, а группа b и d содержат только по одному состоянию. Все состояния, входящие в каждую из этих групп, можно заменить одним состоянием той же группы. Взяв в качестве представителей групп состояния 0, 1, 3 и 6 и обозначив их символами a 0, a 1, a 2 и a 3соответственно, получим следующую таблицу переходов с минимальным числом внутренних состояний.
Для построения автомата Мили воспользуемся рассмотренным ранее алгоритмом, для чего в каждую клетку совмещенной таблицы переходов и выходов запишем значения выходного сигнала, которым отмечено, находящееся здесь состояние.
В полученной таблице колонки, помеченные состояниями a 0 и a 2, a 1 и a 3 идентичны, что позволяет при минимизации исключить состояния a 2 и a 3. В результате получаем таблицу переходов и выходов автомата Мили, имеющего два состояния a 0 и a 1.
ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования... Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом... Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|