Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Топ:
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Дисциплины:
2018-01-29 | 229 |
5.00
из
|
Заказать работу |
|
|
Два автомата, у которых входные и выходные алфавиты совпадают или равнозначны, называют эквивалентными, если любое входное слово оба автомата перерабатывают в совпадающие выходные слова, при условии что перед началом работы оба автомата находились в начальном состоянии.
Построение автомата Мили эквивалентного заданному автомату Мура.
Пусть задан автомат Мура: Ao = <Po, So, s0o, φo, Wo, ψo>.
Найти автомат Мили: A = <P, S, s0, φ, W, ψ>.
Из определения эквивалентности следует: P = Po, W = Wo, s0 = s0o.
Как в автомате Мура, так и в автомате Мили следующие состояние зависит от текущего состояния и текущего входного символа:
в автомате Мура - sko (t+1) = φo(sio(t), pjo(t));
в автомате Мили - sk (t+1) = φ (si (t), pj (t)).
Из этого следует что. функция перехода автомата Мили совпадает с функцией перехода автомата Мура при одном и том - же входном символе. При этом число состояний и функций переходов не изменится т.е.:
S = So и φ (si,pj) = φo(sio,pjо).
В автомате Мили выходной символ wk(t+1) определяется текущим состоянием si(t) и входным символом pj(t):
wk(t+1) = ψ(si(t), pj(t))
В автомате Мура выходной символ wko(t+1) определяется следующим состоянием sko(t+1):
wkо(t+1) = ψo(sko (t+1)), а это состояние: sko(t+1) = φo (sio(t), pjo(t))
Если подставить это выражение для so(t+1) в функцию выхода автомата Мура получим его определение через старое состояние:
wkо(t+1) = ψo(sko (t+1)) = ψo(φo(sio (t), pjo(t)), а так как φ (si,pj) = φo(sio,pjо), то для обеспечения условий эквивалентности необходимо выходные символы автомата Мили, получаемые на переходах в новые состояния сделать равными выходным символам автомата Мура этих состояний и в результате получаем: wk(t+1) = ψ(si(t), pj(t)).
Преобразование автомата Мура в автомат Мили удобно производить в графическом представлении автоматов. Для этого необходимо выходные символы, которыми помечены вершины графа автомата, перенести на все дуги входящие в каждую вершину.
|
Например, пусть задан граф автомата Мура (рис.2.10).
siо/* |
s2о/w1о |
s1о/w2оо |
p2о |
p1о |
p1о |
p2о |
p2о |
Рис.2.10
После переноса выходного символа из каждой вершины на каждую дугу, входящую в эту вершину, получим граф автомата Мили (рис.2.11).
s0 |
p2 / w2 |
s1 |
s2 |
p1 / w2 |
p2/ w1 |
p1 / w2 |
p2 / w1 |
Рис.2.11
Построение автомата Мура эквивалентного заданному автомату. Мили
Пусть задан автомат Мили: A = <P, S, s0, φ, W, ψ>.
Найти автомат Мура: Ao = <Po, So, s0o, φo, Wo, ψo>.
Из определения эквивалентности следует: Po = P, Wo = W, s0 o = s0.
Как в автомате Мили, так и в автомате Мура следующие состояние зависит от текущего состояния и текущего входного символа:
в автомате Мили - sk (t+1) = φ (si (t), pj (t));
в автомате Мура - sko (t+1) = φo(sio(t), pjo(t)).
Из этого следует, что функция перехода автомата Мура аналогична функции перехода автомата Мили при одном и том - же входном символе. Однако так как в автомате Мура выходной символ wko(t+1) определяется следующим состоянием sko(t+1), то каждому состоянию может соответствовать только один выходной символ. Таким образом, если в исходном автомате Мили существуют переходы в одно и то же состояние с выдачей различных выходных символов, то в эквивалентном ему автомате Мура число состояний и соответственно число функций переходов увеличится т.е.:
[ So ] S ] и φo(sio,pjо) φ (si,pj).
Преобразование автомата Мили в автомат Мура можно производить при графическом представлении автоматов. Для этого необходимо выполнить действия обратные действиям при преобразовании автомата Мура в автомат Мили т.е. выходной символ, которым помечена дуга графа автомата перенести в вершину, в которую эта дуга входит.
Например, для фрагмента графа автомата Мили (рис.2.12), сделав такой перенос, получим фрагмент графа автомата Мура (рис.2.13).
|
si |
sj |
pk / wk |
Рис.2.12
si/* |
sj/wk pk |
pk |
Рис.2.13
Для фрагмента графа автомата Мили на рис.2.14 такой перенос осуществить нельзя, так как на каждом переходе происходит выдача различных выходных символов. В этом случае состояние sm необходимо расщепить (продублировать) на такое количество состояний, сколько различных входных символов имеется на всех входных ребрах этого состояния, и сопоставить каждому из них свой выходной символ (рис.2.15).
si |
sj |
sk |
sm |
pi / wi |
pj /wj Wwj |
pk / wk |
pi / wi |
Рис.2.14
si |
sm1/wi |
pi |
sk |
sm3/wk |
pk |
sj |
sm2/wj |
pj |
Рис.2.15
В общем случае при переходе к автомату Мура число состояний может увеличиваться и если одно и то же устройство описывается разными моделями автоматов, то в модели автомата Мура может быть больше число состояний.
Рассмотрим переход от автомата Мили, представленного ранее (рис. 2.9), к модели автомата Мура (рис. 2.16).
Автомат Мили:
p1 / w0 |
p2 / w0 |
p1 / w0 |
p2 / w1 |
p2 / w0 |
s0 |
s1 |
s2 |
p1 / w0 |
Автомат Мура:
s0/w0 |
p11 |
p1 |
s12/wo |
s2/wo |
p1 |
p2 |
s11/w1 |
p2 |
p1 |
p2 |
p21 |
Рис. 2.16
Состояние s1 автомата Мили в процессе перехода было расщеплено на s11 и s12 автомата Мура. Из сравнения автомата Мура (рис. 2.9) с автоматом на рис. 2.16 видно, что это один тот же автомат, для которого ранее было проведено моделирование, и результат работы (табл. 2.5) совпадает с результатом работы автомата Мили (табл. 2.10). т.е. эти автоматы эквивалентны.
Частичные или не полностью определенные автоматы.
Пусть P = {p0, p1, …, pn} – входной алфавит;
* - множество всех слов в алфавите P;
*g – множество допустимых слов ( *g *). Это множество входных слов, для которых определено множество выходных слов;
*z = \ *g - множество запрещенных слов.
Автомат называется частичным или не полностью определенным, если множество запрещенных слов не пусто: *g .
В таблице переходов и выхода такого автомата будут прочерки, означающие отсутствие переходов.
Пример: таблица переходов и выхода (табл. 2.11) и граф (рис. 2.17) частичного автомата Мили.
Таблица 2.11
pj si | p1 | p2 | p3 | ||
s0 | s1/w1 | --- | --- | ||
s1 | --- | s2/w1 | s2/w2 | ||
s2 | --- | s0/w3 |
| ||
s3 | --- | s0/w1 |
|
s3 |
s2 |
p3 / w1 |
p3/w2 |
p2/w1 |
p2/w3 |
p3/w3 |
p2/w1 |
|
Рис. 2.17
В графе частичного автомата Мили будут отсутствовать дуги, соответствующие отсутствующим переходам.
|
|
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!