22104

Методы абстрактного синтеза

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Задача абстрактного синтеза заключается в составлении таблиц переходов и выходов автоматов по заданным условиям его функционирования представленным в форме регулярных выражений. Построенный по этим таблицам автомат обычно содержит лишние внутренние состояния. На втором этапе производится минимизация количества внутренних состояний заданного автомата. Синтезируемый автомат может быть задан либо как автомат Мура либо как автомат Мили.

Русский

2013-08-04

40 KB

0 чел.

Лекция 7

Методы абстрактного синтеза.

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

Абстрактный синтез обычно выполняется в два этапа:

  1.  Первый этап заключается в получении таблиц переходов и выходов в некоторой исходной форме. Построенный по этим таблицам автомат обычно содержит «лишние» внутренние состояния.
  2.  На втором этапе производится минимизация количества

внутренних состояний заданного автомата.

Синтезируемый автомат может быть задан либо как автомат Мура,

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

Рассмотрим пример абстрактного синтеза автомата для случая, когда регулярные отношения составлены без применения операции итерации. Составим отмеченную таблицу переходов автомата, имеющего входной алфавит X{x1, x2} и реализующий следующий алгоритм.

 S1 = x1x2 v x1x1x1 y1   Sзапр. =x1 v x2x2x2

              

S2 = x1x2x2 v x2x2 y2   S4 = S1 v S2 v S3 e.

При синтезе условимся начальное состояние автомата обозначать цифрой 0, а остальные состояния – десятичными числами 1, 2, 3 и т.д. Очевидно, самый простой, хотя и не экономный по числу используемых внутренних состояний автомата, алгоритм синтеза заключается в следующем. Фиксируется начальное состояние и для входного слова , содержащего r букв, назначается r внутренних состояний. Переходы в автомате определяются так, что первая буква входного слова переводит автомат из начального состояния 0 в состояние 1, вторая буква из 1 в 2 и т.д. Аналогичные последовательности внутренних состояний назначаются для всех остальных слов. Затем все конечные состояния, в которые автомат попадает после подачи слов, входящих в событие Si, отмечаются выходными сигналами yi.

Чтобы система переходов автомата была определенной, для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. Например, для регулярного события S1 первая буква x1 переводит автомат из начального состояния 0 в состояние 1, вторая буква x2 – из 1 в 2.

S = x1 x2 v x1 x1 x1

     0    1     2   0   1   3    4

S = x1 x2 x2 v x2 x2

     0    1     2    5    0    6    7

Поскольку первая буква второго слова x1x1x1, входящего в S1 также есть x1, то она переводит автомат из начального состояния 0 в 1. Вторая буква x1 переводит автомат из 1 в 3, третья – из 3 в 4.

Первые две слова x1x2x2, входящего в  S2, совпадают с первым словом события S1. Поэтому первые две буквы этого слова должны последовательно переводить автомат из 0 в 1, и из 1 в 2. Дальнейшие состояния обозначим числами 5, 6 и 7. Получившаяся в результате форма записи определяет разметку мест регулярных выражений.

Местами регулярного выражения называют промежутки между двумя буквами, между буквой и знаком дизъюнкции, а так же между буквой и скобкой. Кроме того, вводят начальное место, обозначаемое цифрой 0 и конечные места, отождествляемые с концом каждого слова. Для запрещенного события Sзапр последовательность событий можно не назначать.

Для размеченных регулярных выражений составляется отмеченная таблица переходов.

e

e

y1

e

y1

y2

e

y2

E

xj\ai

0

1

2

3

4

5

6

7

*

x1

1

3

*

4

*

*

*

*

*

x2

6

2

5

*

*

*

7

*

*

Чтобы система переходов автомата была определена при подаче любого входного слова, кроме состояний 0 7, вводится еще одно состояние, которое обозначается звездочкой *. В это состояние автомат переходит при подаче входных слов, которые не входят в события S1 и  S2. Выходным сигналом y1 отмечены состояния 2 и 4, y2 – состояния 5 и 7. Остальные состояния отмечены пустой буквой e.

Алгоритм синтеза усложняется, если регулярные выражения содержат итерационные скобки.

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

Все места регулярного выражения, слева от которых стоит буква, а так же все начальные места называют основными.

Все места, справа от которых стоит буква, называют предосновными. Очевидно, некоторые места могут быть одновременно основными и предосновными.

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

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

S = { x2 v x1 x2 v x1 x1 x2} x1 x1 x1 { x1 } x2  

     0       1         2    3        4    5    6        7   8    9       10     11

  

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

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

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

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

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


 

А также другие работы, которые могут Вас заинтересовать

22275. Самодержавие и реформы в России во второй половине XIX, в начале XX века 284 KB
  Первые шаги к отмене крепостного права в России были сделаны императором Александром I в 1803 году изданием Указа о вольных хлебопашцах, в котором прописан юридический статус отпускаемых на волю крестьян.
22276. СМЕШАННЫЕ ДИСТРОФИИ (СД) 39 KB
  НАРУШЕНИЯ ОБМЕНА ХРОМОПРОТЕИДОВ Хромопротеиды или эндогенные пигменты делят на три группы гемоглобиногенные ферритин гемосидерин билирубин гематоидин гематины порфирин. Нарушения обмена гемоглобиногенныз пигментов В норме при распаде эритроцитов гемоглобин превращается в пигменты красящие вещества: ферритин гемосидерин билирубин При патологии изза усиленного гемолиза распад эритроцитов могут образовываться новые пигменты: гематоидин гематины порфирины. Среди нарушенного обмена...
22277. СТРОМАЛЬНО-СОСУДИСТЫЕ ДИСТРОФИИ 42.5 KB
  Мукоидное набухание Определение – это нетяжелая обратимая дезогранизация соединительной ткани. В норме в соединительной ткани белки и гиалуроновая кислота находятся в связанном состоянии в виде белковополисахаридных комплексов. Это ведет к набуханию волокон соединительной ткани и набуханию основного вещества. Микро Набухает основное вещество и волокна соединительной ткани.
22278. ТУБЕРКУЛЕЗ. Первичный туберкулезный комплекс (ПТК) 35 KB
  Вызывает туберкулез микобактерия туберкулеза палочка Коха. Туберкулез подразделяют на первичный гематогенный и вторичный. Первичный туберкулез – туберкулез у людей впервые инфицированных микобактерией характеризующийся возникновением первичного туберкулезного комплекса первичный аффект лимфангит лимфаденит.
22279. ТУБУЛОПАТИИ. Острая тубулопатия или острый некротический нефроз 36 KB
  Макро: почки увеличены набухшие отечные корковый слой бледносерый мозговой – темнокрасный. Больные чаще всего погибают в первые две стадии от уремии но с помощью искусственной почки большинство больных можно спасти. ПИЕЛОНЕФРИТ Определение: пиелонефрит – это воспалительное бактериальное заболевание с поражением лоханки пиелит и межуточной ткани почки. нисходящий гематогенный механизм – возбудитель попадает в почки из первичного внепочечного очага воспаления ангина пневмония и т.
22280. ХРОНИЧЕСКИЕ НЕСПЕЦИФИЧЕСКИЕ ЗАБОЛЕВАНИЯ ЛЕГКИХ (ХНЗЛ) 41 KB
  Классификация ХНЗЛ В группу ХНЗЛ входят следующие болезни: Хронический бронхит Бронхоэктазы Хроническая пневмония Эмфизема легких Хронический абсцесс легкого Пневмосклероз Интерстициальные болезни легких ИБЛ. Выделяют 3 патогенетические механизма ХНЗЛ: Бронхитогенный механизм – в основе хронический бронхит и его осложнения бронхоэктазы пневмосклероз эмфизема. Исходы и осложнения: бронхоэктаз Эмфизема Пневмосклероз. ЭМФИЗЕМА ЛЕГКИХ Определение: эмфизема – это повышенное содержание воздуха в легких и увеличение их...
22281. Эндокринопатии Клинико-морфологические формы 24 KB
  По гистологическому строению зоб бывает колллоидным макрофолликулярным микрофолликулярным и смешанным и паренхиматозным Клиникоморфологические формы зоба: Эндемический зоб возникающий в определенных местах где мало йода в воде. Спорадический зоб появляется в молодом возрасте и у взрослых. Базедов зоб базедова болезнь – названа по фамилии немецкого врача – Базедов.
22282. БОЛЕЗНИ ПЕЧЕНИ 40.5 KB
  ГЕПАТОЗЫ – это болезни печени характеризующиеся дистрофией и некрозом гепатоцитов. ГЕПАТИТЫ – заболевания печени в основе которого лежит воспаление проявляющееся как в дистрофии и некрозе гепатоцитов так и в клеточной инфильтрации стромы. ОПУХОЛИ – болезни печени с развитием в ткани печени опухолевого процесса первичного или вторичного происхождения метастазы в печени.
22283. БОЛЕЗНИ ПОЧЕК (НЕФРОПАТИИ) 35.5 KB
  Гломерулопатии – это заболевания которые характеризуются первичными воспалительными или дистрофическими поражениями клубочков гломерул почек что ведет к нарушению функции фильтрации. Классификация гломерулопатий: гломерулонефриты нефротический синдром амилоидоз почек диабетический гломерулосклероз печеночный гломерулосклероз. Гломерулонефриты – это группа заболеваний почек для которых характерно: двухсторонний процесс воспалительные негнойные поражения клубочков гломерул почечные симптомы – гематурия эритроциты в моче...