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

Второй пример абстрактного синтеза

Читайте также:
  1. II. Методы непрямого остеосинтеза.
  2. IV. Современные методы синтеза неорганических материалов с заданной структурой
  3. X. примерный перечень вопросов к итоговой аттестации
  4. XX съезд КПСС. Процесс политической реабилитации и десталинизации во второй половине 1950 – начале 1960-х гг. и его значение.
  5. А) Закон диалектического синтеза
  6. Абстрактного к конкретному
  7. Актерское искусство второй половины XIX века
  8. Алгоритм синтеза автомата Мура
  9. Антигоспитальное в области психиатрии движение в мире во второй половине XX века
  10. Археологические исследования второй половины XIX – первой трети XX вв. (с.43)
  11. Бактериальный фотосинтез. Отличия бактериального фотосинтеза от фотосинтеза растений
  12. Белорусские города во второй пол 13 – первой пол 17 вв. Развитие ремесла и торговли.

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

 


Регулярные выражения событий S 1 и S 2 содержат одинаковые сомножители в итерационных скобках, перед которыми расположено место с индексом 0. Поэтому в обоих выражениях основные места внутри итерационных скобок отмечены одинаковыми индексами (3, 4 и 5). Индекс конечного места каждого выражения распространяется на начальные места всех регулярных выражений, так как в автоматах многократного действия за словом любого события, например S 1, может быть подано слово любого другого события, то есть S 1 v S 2 v S 3. В размеченных выражениях можно объединить места с индексами 4, 6 и 5, 9:


 


По размеченному выражению составим отмеченную таблицу переходов:

yg е е y 3 е е е е y 1 е y 2 е е е е
xj / ai                     1v3 3v6 3v8 *
xr 1v3   1v3   3v6 3v8   1v3   1v3 1v3 3v6 3v8 *
x 01   *         *   *         *
x 10   *         *   *         *
xs       *                   *

 

При составлении таблицы следует учитывать, что для разных регулярных выражений автомат под действием одних и тех же входных сигналов переходит в разные состояния. Эти внутренние состояния будем отмечать множеством индексов основных мест. Например, в событии 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.

 

yg e e y 3 e e e e y 1 e y 2 e
xj /ai                      
xr                      
х 01                      
х 10                      
xs                      

 

По построенной таблице проведем третий этап минимизации, исключив такие состояния, в которые автомат из нулевого состояния никогда перейти не может. В нашем случае такими состояниями являются 1, 3, 6, 8 и 10.

Обозначив оставшиеся состояния 0 – b 0, 2 – b 1, 4 – b 2, 5 – b 3, 7 – b 4, 9 – b 5, получим окончательную таблицу переходов заданного автомата:

yg e y 3 e e y 1 y 2
xj / ai b 0 b 1 b 2 b 3 b 4 b 5
xr b 0 b 0 b 2 b 3 b 0 b 0
x 01 b 2 b 2 b 2 b 2 b 2 b 2
x 10 b 3 b 3 b 3 b 3 b 3 b 3
xs b 1 b 1 b 4 b 5 b 1 b 1

 

 


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.003 сек.)