Реакция автоматов на входное слово[править]
Автомат Милиправить
Допустим, входное слово поступает на вход автомата буква за буквой.
Выходное слово называется реакцией автомата Мили на входное слово в состоянии строится по таблице переходов и выходов).
Реакцию автомата на входное слово можно заменить обходом графа.
Автомат Мураправить
Выходное слово называется реакцией автомата Мура на входное слово в состоянии .
В рассматриваемом примере для автоматов Мили и Мура реакции автоматов на одинаковое входное слово совпадают, но они сдвинуты на один такт. Автоматы Мили и Мура дающие одинаковые реакции на одинаковые входные слова называются эквивалентными. Данное замечание приводит к задаче построения эквивалентных автоматов, дающих одинаковые реакции на одинаковые входные слова.
Формальное определение
Автомат Мура можно определить как набор из семи элементов :
А.знак равно(Q,Σ,Ω,δ,λ,q,Ф.){\ displaystyle {\ mathcal {A}} = \ left (Q, \ Sigma, \ Omega, \ delta, \ lambda, q_ {0}, F \ right)}
- Q{\ displaystyle Q}- конечный набор состояний .(|Q|<∞){\ Displaystyle \ влево (\ влево | Q \ вправо | <\ infty \ вправо)}
- Σ{\ displaystyle \ Sigma}это входной алфавит. ,|Σ|<∞{\ Displaystyle \ влево | \ Sigma \ вправо | <\ infty}Q∩Σзнак равно∅{\ Displaystyle Q \ cap \ Sigma = \ emptyset}
- Ω{\ displaystyle \ Omega} — выходной алфавит. |Ω|<∞{\ Displaystyle \ влево | \ Омега \ вправо | <\ infty}
- δ{\ displaystyle \ delta} функция перехода δQ×Σ→Q{\ displaystyle \ delta: Q \ times \ Sigma \ rightarrow Q}
- λ{\ displaystyle \ lambda} определяет функцию вывода: λQ→Ω{\ displaystyle \ lambda: Q \ rightarrow \ Omega}
- q∈Q{\ displaystyle q_ {0} \ in Q} это начальное состояние.
- Ф.⊆Q{\ Displaystyle F \ substeq Q}представляет собой (конечный) набор возможных принимающих состояний (= набор конечных состояний). Если автомат останавливается в одном состоянии после прочтения входного слова , он является частью языка .J∈Σ*{\ Displaystyle J \ in \ Sigma ^ {*}}Ф.{\ displaystyle F}J{\ displaystyle J}Л.(А.){\ Displaystyle L \ влево (А \ вправо)}
Если обычный язык машины не представляет интереса, его можно не учитывать. Тогда автомат определяется как шестерка.
Ф.{\ displaystyle F}
Число состояний машины Мура не меньше числа состояний соответствующей машины Мили .
Резюме
Предложенный в настоящей статье движок может быть, разумеется, доработан.
Из возможных дополнений отметим лишь несколько самых важных:
Не помешает добавить обработку команд, которые соответствуют петлям графа переходов,
а также вообще не предусмотренные для данного автомата. Такие команды не изменяют текущее состояние.
Простейший вариант реализации этого состоит в небольшой модификации метода input:
this.input=function(inp){ // ввод команд
if (inp&&this.trans){ ...}
...
}
В движок автомата можно добавить регистрацию обработчиков событий, на которые он должен реагировать как на команды.
Например, для современных браузеров, отличных от IE 8 и более ранних версий, можно использовать стандартный метод
htmlElement.addEventListener(событие, функция-обработчик, false)
Для IE 8 и более старых можно использовать метод
htmlElement.attachEvent(событие, функция-обработчик)
Возможно, потребуются переменные и/или вспомогательные объекты для хранения промежуточных значений.
Автомат — миля
|
Взаимодействие управляющего автомата и операционного блока.| Схема выделения состояний управляющего автомата. |
Автомат Мили, построенный по микропрограмме, имеет чис-ло состояний, как правило, меньшее числа состояний эквива-лентного ему автомата Мура. С этой точки зрения использование автомата Мили предпочтительно. Однако применение автомата Мили в качестве управляющего автомата не всегда возможно. У автомата Мили переход в новое состояние осуществляется одновременно с формиро-ва Гем выходного сигнала. Поэтому, если ОБ вырабатывает оповещающие сигналы и… Мили, возможна следующая недопустимая ситуация: автомат Мили еще не сменил состояние, а на его входы пришли новые значения оповещающих сигналов, требующие выполнения иного перехода.
Автомат Мили, построенный по микропрограмме, имеет число состояний, как правило, меньшее числа состояний эквивалентного ему автомата Мура. С этой точки зрения использование автомата Мили предпочтительно. У автомата Мили переход в новое состояние осуществляется одновременно с формированием выходного сигнала. Мили, возможна следующая недопустимая ситуация: автомат Мили еще не сменил состояние, а на его входы пришли новые значения оповещающих сигналов, требующие выполнения иного перехода.
Автомат Мили имеет число состояний, меньшее, чем автомат Мура, однако его комбинационная схема может оказаться сложнее. При сравнении моделей необходимо также учитывать, что у автомата Мили выходной сигнал формируется одновременно с переходом автомата в новое состояние, что может затруднить сопряжение работы УА и ОА во времени.
Почему автомат Мили не всегда может использоваться в качестве управляющего автомата.
|
Микропрограммный автомат на элементах задержки. |
Поскольку автомат Мили имеет число состояний меньшее, чем число состояний эквивалентного ему автомата Мура, то путем построения автомата по схеме Мили может быть достигнута экономия в числе запоминающих элементов.
Пусть автомат Мили задан таблицей переходов и таблицей выходов ( табл. 3.5), где в клетках таблицы переходов записаны состояния, в которые переходит автомат из исходного состояния при соответствующем входе, а в клетках таблицы выходов записывается выход при тех же условиях. Нетрудно видеть, что приведенный пример соответствует реверсивному счетчику, причем выходы Y1 и Y2 соответствуют выдаче сигналов переноса.
Поэтому автоматы Мили и Мура обладают равными функциональными возможностями в том смысле, что всякое преобразование дискретной информации, осуществляемое в одном из них, осуществимо и в другом.
Для автомата Мили на каждом входном векторе надо проверять и выходные вектора и внутренние состояния, если они доступны.
|
Граф-автомата Мили а2 и отмеченные сигналами x2 / yz и. |
Граф автомата Мили определяется по отмеченному графу микропрограммы ( см. рис. 5.2) следующим образом. На рис. 5.3 проставляются вершины графа, соответствующие состояниям а, аъ а2, а3 автомата.
Два автомата Мили тогда и только тогда эквивалентны между собой ( в смысле совпадения индуцируемых ими автоматных отображений), когда эквивалентны их начальные состояния.
В автомате Мили с начальным состоянием а0 связана некоторая совокупность выходных сигналов, по которым выполняются соответствующие микрооперации. В связи с этим переходы в автомате Мура должны происходить в начале такта по поступлении запускающего сигнала Z. При необходимости граф автомата Мили может быть дополнен начальным состоянием ан. Окончанию операции соответствует переключение автомата в исходное состояние ан.
Закон функционирования автомата Мили может задаваться с использованием совмещенной таблицы переходов и выходов. В этом случае в клетках таблицы указываются значения функции переходов и функции выходов в виде AIY.
Формальное определение
Машина Мура — это кортеж из шести
- (Q,я,В,B,δ,λ){\ displaystyle (Q, я, A, B, \ delta, \ lambda)}
сделано из :
- конечный набор состояний ;Q{\ displaystyle Q}
- начальное состояние , элемент ;я{\ displaystyle i}Q{\ displaystyle Q}
- конечное множество , называется входной алфавит;В{\ displaystyle A}
- конечное множество , называется выходной алфавит;B{\ displaystyle B}
- переход функции ;δQ×В→Q{\ displaystyle \ delta: Q \ times от A \ до Q}
- выходная функция .λQ→B{\ displaystyle \ lambda: Q \ to B}
Состояние удобно отмечать с помощью, а символ вывода — с помощью . Функция перехода и функция вывода расширяются до слов по индукции, для и с помощью
δ(q,в){\ Displaystyle \ дельта (д, а)}q⋅в{\ displaystyle q \ cdot a}λ(q⋅в){\ Displaystyle \ лямбда (д \ CDOT а)}q⋆в{\ displaystyle q \ star a}В*{\ displaystyle A ^ {*}}ш∈В*{\ Displaystyle ш \ в А ^ {*}}в∈В{\ displaystyle a \ in A}
- q⋅швзнак равно(q⋅ш)⋅в,q⋆швзнак равно(q⋆ш)((q⋅ш)⋆в).{\ displaystyle q \ cdot wa = (q \ cdot w) \ cdot a, \ quad q \ star wa = (q \ star w) ((q \ cdot w) \ star a).}
Другими словами, вывод, производимый словом , прочитанным из состояния , является словом, произведенным словом , прочитанным из состояния , за которым следует буква, связанная с состоянием, достигнутым после чтения .
шв{\ displaystyle wa}q{\ displaystyle q}ш{\ displaystyle w}q{\ displaystyle q}q⋅шв{\ displaystyle q \ cdot wa}шв{\ displaystyle wa}
Функция , выполняемая с помощью автомата Мура является применение определяется по формуле:
жВ*→B*{\ displaystyle f: A ^ {*} \ to B ^ {*}}
- ж(ш)знак равноя⋆ш{\ Displaystyle F (ш) = я \ звезда ш}
Следовательно, это функция, которая со словом of , считываемым из начального состояния , связывает слово on, полученное путем конкатенации букв, связанных с состояниями прибытия пройденных переходов.
ш{\ displaystyle w}В*{\ displaystyle A ^ {*}}я{\ displaystyle i}B*{\ displaystyle B ^ {*}}
Варианты
Иногда машина Мура имеет конечный набор конечных состояний . Затем выполняемая функция ограничивается словами рационального языка во входном алфавите, распознаваемом автоматом. Тогда язык слов, производимых функцией, является рациональным языком .
ж{\ displaystyle f}ж{\ displaystyle f}
Обычно переходная функция является полной; когда он частичный, отсутствие перехода приводит к блокировке ПЛК.
δQ×В→Q{\ displaystyle \ delta: Q \ times от A \ до Q}
Цифровая технология
Автомат Мура в цифровых технологиях
Машину Мура можно реализовать с помощью цифровых технологий. Для этого требуются две коммутационные сети и блок памяти с синхронизацией. В дополнение к логическим модулям, подключенным к печатной плате, реализация часто осуществляется с использованием программируемой логики и использования языка описания оборудования .
Обработка с помощью логических схем требует преобразования входного и выходного алфавита в двоичный код, аналогичный приведенной ниже таблице.
|
|
|
Программная реализация автомата Мили
автомат Миликоманда
var front=function() {document.getElementById('myimg').src="front.jpg"};
var left=function() {document.getElementById('myimg').src="left.jpg"};
var right=function() {document.getElementById('myimg').src="right.jpg"};
var back=function() {document.getElementById('myimg').src="back.jpg"};
out=[]; // массив выходов автомата
out=[];
out=left;
out=right;
out=back;
out=[];
out=back;
out=front;
out=right;
out=[];
out=front;
out=back;
out=left;
out=[];
out=right;
out=left;
out=front;
function automat2(trans,out,stat){ // движок автомата Мили
this.trans=trans; // массив переходов
this.out=out; // массив выходов
this.stat=stat; // текущее состояние
this.input=function(inp){ // ввод команд
if (inp){
this.output=out // выход
this.output(); // вычисление выхода
this.stat=this.trans;
}
return this.stat
}
}
Проблема
В упомянутой статье Мур рассматривает машины типа ( n ; m ; p ). Это автоматы, имеющие n состояний, m входных символов и p выходных символов. В разделе « Дальнейшие задачи » в конце статьи он предлагает изучить следующую задачу: «Улучшение оценок, приведенных в теоремах 8 и 9». Теорема 8 выглядит следующим образом:
Теорема 8 — Для машины типа ( n ; m ; p ) такой, что любые два ее состояния различимы, существует эксперимент длины, который определяет состояние в конце эксперимента.
нет(нет-1)2{\ Displaystyle п (п-1) / 2}
Анатолий Алексевич Карацуба решил задачу Мура об усовершенствовании указанного терминала, доказав в 1957 году, когда он был студентом механического факультета МГУ им. М.В. Ломоносова , следующий результат:
Теорема — Учитывая машину типа ( п ; м ; р ) , так что любые два из его состояний различимы, есть длина эксперимент , который определяет состояние в конце эксперимента. Кроме того, этот предел достигнут.
(нет-1)(нет-2)2+1{\ Displaystyle (п-1) (п-2) / 2 + 1}
Этот результат был опубликован в 1960 году.
Программная реализация автомата Мура
Функции переходов и выходов можно представить таблицами, а реализовать их программно — с помощью ассоциативных массивов, индексы которых представляются символьными строками,
содержащими имена состояний и команд. Далее рассматривается, как это сделать.
Переходы состояний
var trans=; // массив переходов состояний автомата trans=; trans="левая"; trans="правая"; trans="зад"; trans=; trans="зад"; trans="анфас"; trans="правая"; trans=; trans="анфас"; trans="зад"; trans="левая"; trans=; trans="правая"; trans="левая"; trans="анфас";
Выходы состояний
src<img id=’myimg’ …>
var out=; // массив выходов автомата
out =function() {document.getElementById('myimg').src="front.jpg"}
out =function() {document.getElementById('myimg').src="left.jpg"}
out=function() {document.getElementById('myimg').src="right.jpg"}
out =function() {document.getElementById('myimg').src="back.jpg"}
Движок
automattransoutstatstatinput(команда)output()
function automat(trans,out,stat){ // движок автомата
this.trans=trans; // массив переходов
this.out=out; // массив выходов
this.stat=stat; // текущее состояние
this.input=function(inp){ // ввод команд
if (inp){
this.stat=this.trans;
this.output=out // выход
}
return this.stat
}
this.output=out;// выход
}
myautomat=new automat(trans,out,"анфас") // создание экземпляра объекта automat
myautomat.input("налево") // выдача команды
myautomat.output() // вычисление выхода
myautomat.input("налево");myautomat.input("налево");myautomat.input("налево");
myautomat.output()
<input type="button" value="направо"
onclick="myautomat.input(this.value);myautomat.output()"/>
<input type="button" value="налево"
onclick="myautomat.input(this.value);myautomat.output()"/>
<input type="button" value="кругом"
onclick="myautomat.input(this.value);myautomat.output()"/>
function automat(trans,out,stat){ // движок автомата
this.trans=trans; // массив переходов
this.out=out; // массив выходов
this.stat=stat; // текущее состояние
this.input=function(inp){ // ввод команд
if (inp){
this.stat=this.trans;
this.output=out // выход
this.output(); // вычисление выхода
}
return this.stat
}
this.output=out;// выход
this.output(); // вычисление выхода
}
