Определение реакции автомата на входное слово
Пусть на вход автомата Мили АА и эквивалентного ему автомата Мура АВ из примера 4.3 поступает входное слово 
. Рассмотрим реакцию автоматов на входное слово.
Для автомата Мили имеем: 
; 
, т.е. под действием символа х1 автомат переходит в состояние 
с выходом у1; при следующем символе 
получим: 
; 
и т. д. В результате получим последовательность состояний и выходное слово:
| входное слово x |  — | = k * |
| cостояния S |  | = k+1 |
| выходное слово h |  — | = k |
Для автомата Мура АВ имеем: при вхождении символа х1 автомат находился в состоянии с выходом 
, 
; 
. Далее поступает следующий символ х1 в состоянии 
с выходом и т.д. Последовательность входных и выходных символов, а также символов состояний выглядит аналогично представленным выше для автомата Мили:
| входное слово x | — | = k |
| cостояния S |  | = k+1 |
| выходное слово h |  | = k+1 |
Видно, что реакция автоматов АА и АВ на входное слово 
совпадают с точностью до сдвига на один такт; это получилось потому, что реакция автомата Мура на входную букву наступает в следующем такте. Так будет и в общем случае, если автоматы эквивалентны и разных типов. Проверка этого утверждения предоставляется студентам.
Определение входного слова автомата по его начальному состоянию и выходному слову
Изложенный в разделе 14.2 метод при некоторой модификации может быть применен для нахождения входного слова Q, по заданным начальному состоянию и выходному слову z=y(l),y(2). y(k), автомата A=(X,S,Y,(hx)X€x,(fx)x€x). То есть требуется найти хотя бы одно решение уравнения A(s,Q)=z относительно неизвестного QeX k . При этом предполагается известной мощность | R(A,z) | множества R(A,z) решений данного уравнения. В обозначениях 5.1 мы здесь положили
Для решения этой задачи строим вспомогательный автомат А* — статистический аналог автомата А:
Назовем входное слово Q=x(l),x(2). x(k) А,А*,s-непротиворечивым, если пара (s,Q) А,А*- непротиворечива и А,А*,s-противоречивым, если пара (s, Q) А, А*,s-противоречива.
Через R(A,s,z), и R(A*,s,z) обозначим, соответственно, множества решений Q уравнений
где R n P(A,s,z), R Hen P(A,s,z), соответственно, множества А,А*,s-противоречивых и A,A*,s- непротиворечивых входных слов из R(A,s,z). Считаем известным множество R(A*), для которого 
и предполагаем, что множество R Hen P(A,s,z) непустое. При равновероятном распределении на Х к , очевидно
Через М(Х к —>Y k ) обозначим множество всех отображений П=Х к в Z= Y k , таких, что отображение ср чч еМ(Х к —>Y k ) тогда и только тоща, если
где R(cp»,z) — множество решений уравнения (p»(oo)=z, и одновременно | R(A,z) | = | R(cp vv ,z) |. Предположим, что на M(X k —>Y k ) и Х к задано равномерные вероятностные меры. Получаем
Нахождение входного слова Q (или всех слов Q), для которого A(s, Q)=z, проводится с помощью алгоритмов, полностью аналогичных приведенным ранее, в разделах 14.1, 14.2.
Так же используется и вероятность Ps к для расчета средней трудоемкости алгоритмов.
Несколько замечаний следует сделать относительно расчета | R(A,s,z) | и | R Hen p(A,s,z) | и рекомендаций по выбору А*. Именно, при z=y(l),y(2). y(k)
десь использованы обозначения a y ab, *a y b из раздела 14.2.
Выбор наилучшего статистического аналога для автомата А является сложной самостоятельной задачей. В тоже время очевидно, что выбирать статистический аналог А* автомата А следует исходя из следующих соображений:
Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 2
Статья написана, собрана и сверстана Brotherofken. Спасибо ему огромное.
В предыдущей статье я попытался изложить все основные определения и принципы, чтобы сделать эту статью максимально понятной. Все не уместилось, так что я настоятельно советую ознакомиться с этими файлами:
Базис, Базис2, Минимизация. Далее в этой статье я оставил несколько разъясняющих пометок курсивом.
В этой статье я попробую объяснить доступным языком что такое абстрактный автомат, способы его представления. Так как теория автоматов полна математики и сложна, постараюсь писать человеческим языком, чтобы неподготовленный читатель смог понять о чём идёт речь.
- Комбинационные Схемы (КС) – не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.
- Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.
Абстрактный автомат
Автомат должен будет реализовывать некоторые функции, которые заданы разработчиком. Он может быть простым сумматором, может реализовывать какую-либо микрокоманду процессора, выбирать слова из оперативной памяти или заниматься синтаксическим анализом выражения.
В общем виде, не вдаваясь в подробности, абстрактный автомат можно представить следующим образом: 
Или, если перейти от иллюстрации к математическому описанию:
A = <A, B, C, δ, λ>
- Множество – представляет собой множество значений на физических входах автомата. На входе в нашем случае будет какая-то последовательность высоких и низких уровней напряжения, которые будут кодировать логические нули и единицы.
- Множество – представляет собой множество значений на физических выходах автомата.
- Множество
– а множество, которое представляет внутреннее состояние автомата – память. На будущее C0 будем обозначать начальное состояние автомата. - δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние ai в которое переходит автомат из состояния aj.
- λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.
Такой автомат функционирует дискретно по времени, то есть значения входов, выходов и внутреннее состояние автомата изменяются в дискретные моменты времени.
Итак мы в общем виде описали что есть Абстрактный автомат. Примером такого автомата может быть триггер, регистр ЭВМ или сумматор.
- Автоматы Мили. Описывается системой уравнений:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t-1) ). - Автоматы Мура. Описывается уравнениями:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t) ).
Т.е. автомат типа Мили вырабатывает выходной сигнал когда у него меняется входной, в зависимости от его предыдущего состояния. При этом длительность выходного сигнала не зависит от длительности входного, а только от его присутствия. В автоматах типа Мура выходной сигнал зависит от состояния автомата в текущий момент времени т.е. автомат будет вырабатывать определенный выходной сигнал пока не изменит свое состояние.
Способы задания автоматов
Как мы выяснили в первой части — автомат представляет собой совокупность входного и выходного алфавитов, множества внутренних состояний и функций, определяющих переходы и выходы. Однако, обычно функции δ и λ не заданы, и поведение автомата приходится описывать по-другому.
- При помощи графов.
- При помощи таблиц переходов и выходов.
Графы
Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое.
Для графа Мили на дугах указываются сходные и выходные буквы. Выходные буквы пишутся над дугами, символизируя то, что выходное состояние зависит от состояния автомата в предыдущий момент времени.
Для графа автомата Мура на дугах записываются только входные буквы, выходные же указываются около вершин.
Важный момент: Если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат называется полным. Другими словами – если из каждой вершины определены переходы для каждой входной буквы. В наших примерах автомат Мили является полным, а автомат Мура – частичным.
И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется недетерминированным. Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к детерминированному автомату, но это не всегда можно выполнить. Описание этого процесса я тоже упускаю, сразу нарисовав детерминированный автомат.
На этом о графах всё.
Таблицы переходов и выходов.
Графы нагляднее для человека, а таблицы — для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ). В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы.
Построим ТПВ для наших графов Мили и Мура. Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.
ТПВ графа Мили
В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3. 
ТПВ графа Мура
Для графа Мура строят отмеченную таблицу переходов. Выделяется дополнительный столбец для выходных букв.
В клетке под входной буквой пишется в какое состояние автомат переходит, в крайней правой клетке — какую выходную букву возвращает. 
Пример синтеза автомата
При помощи абстрактных автоматов можно описать практически что угодно. Можно описать работу цифровой схемы, а можно – синтаксический или лексический анализатор. Попробуем описать триггер – чем не автомат?
Чтобы задать граф нужно словесное описание алгоритма работы триггера. Читаем:
Кодируем входной и выходной алфавиты:
A =
B =
Строим граф автомата Мили: 
Вот такая забавная чебурашка получилась :-). Теперь можно построить таблицу переходов и выходов: 
Если расписать эту таблицу преобразовав условные обозначения в фактические, то получим таблицу которая представляет из себя таблицу переходов триггера. Затем её можно упростить: 
Нанесём полученную функцию на карту Вейча и минимизируем:
Выпишем, что получилось: 
Строим по функции схему (Выполняли домашнее задание?):
Немного непривычно видеть триггер в булевом базисе, поэтому переведём функцию в базис И-НЕ и нарисуем схему в нём: 
А на схеме асинхронный RS триггер обозначается вот так:
Теперь если приложить немного старания, то можно самостоятельно синтезировать простую новогоднюю гирлянду.
Регулярные грамматики и конечные автоматы
Регулярные грамматики — это грамматики, которые способны точно определить каждый регулярный язык, и по этой причине являются эквивалентными конечному автомату и регулярным выражениям.
Регулярные грамматики способны точно определить каждый регулярный язык, и поэтому являются эквивалентными конечному автомату и регулярным выражениям. Регулярные грамматики выступают как подмножества контекстно-свободных грамматик. Регулярная грамматика может задаваться совокупностью правил в качестве левой или правой регулярной грамматики.
В правой регулярной грамматике весь набор правила может быть в одном из следующих форматов:
- A → a
- A → aB
- A → ε
В левой регулярной грамматике весь набор правил может быть в одном из следующих форматов:
- A → a
- A → Ba
- A → ε
- Большие буквы (A, B) призваны обозначить не терминалы из множества N.
- Строчные буквы (a, b) служат для обозначения терминалов из множества Σ.
- ε должен обозначать пустую строку, то есть строку, имеющую длину нуль.
Класс правой и левой регулярной грамматики считаются эквивалентными, поскольку каждый класс в отдельности является достаточным, чтобы задать все регулярные языки. Каждую регулярную грамматику можно преобразовать из левой регулярной грамматики в правую, и наоборот.
Все контекстно-свободные грамматики могут быть легко преобразованы в вид, в котором присутствуют только правила из лево-регулярной или право-регулярной грамматики. Причём для контекстно-свободной грамматики допускается наличие тех и других грамматик одновременно. Отсюда следует вывод, что такие грамматики способны отобразить каждый из контекстно-свободных языков. Регулярные грамматики способны обладать или лево-регулярными правилами, или право-регулярными правилами, но никак не обоими типами одновременно. То есть, они способны описать только подмножество языков, именуемых регулярными языками.
Готовые работы на аналогичную тему
Регулярные грамматики и конечные автоматы
Конечным автоматом является определённое устройство, которое обладает конечным числом состояний и предназначено для прочтения слов заданного конечного алфавита. По умолчанию считается, что слово занесено на некоторую ленту, составленную из ячеек, в каждую из которых занесена одна буква алфавита. Чтение ленты выполняется в дискретные такты времени в направлении слева направо. Подразумевается, что считывание произвольного слова «a» автомат должен начинать из специально заданного начального состояния. Считывание очередного символа в текущем такте времени должно сопровождаться перемещением вправо к прочтению следующего символа и изменением текущего состояния, которое должно определяться считанной в текущем такте буквой и состоянием, в котором автомат находится в текущем такте. Слово, имеющее длину l, автомат обрабатывает в течение l тактов. Итог прочтения слова «а» должен определяться состоянием, в котором автомат может оказаться после завершения обработки данного слова.
Приведённое в словесной форме описание конечного автомата и его функционирования можно заменить при помощи следующего формального определения. Конечный автомат К * может быть определён с помощью следующего выражения:
- А = <а1, а2, . an>является входным алфавитом.
- Q =
- q0 является выделенным начальным состоянием автомата.
- g является функцией переходов, определенной на множестве QxA = <(qi, 0)\i=l. m; j=1. n>и принимающей значения из множества Q (когда g(qi,aj) = qk, то это значит, что конечный автомат, который находился в состоянии qi , после прочтения буквы aj перешёл в состояние qk).
- F является выделенным подмножеством (Fc Q), то подмножеством «хороших» состояний автомата.
Работа конечного автомата «К» по чтению входного слова а = ai1, ai2,…aip может быть представлена следующим образом. Пусть qa(t) будет обозначать состояние, в котором окажется автомат «К» после t тактов обработки текущего слова (здесь t=0,1,2. р):
- qa (0) = qо (перед началом работы автомат находился в состоянии q0), qa(1) = g(qa(0), ai.1) (прочитав первую букву, автомат переходит в состояние q« (1)).
- qа (2) = g (q a(1), ai2) (прочитав вторую букву, автомат переходит из состояния qa (1) в состояние qа (2)).
- qа(Р) = g(qа(Р — 1), aip) (прочитав все слово, автомат переходит из состояния qa(p-1) в состояние qа (Р)).
Считается, что слово «а» принято автоматом «К», если qa(p)ϵF , то есть после прочтения всего слова автомат должен находиться в одном из «хороших» состояний.
Пусть L(K) является совокупностью слов, которые принимает автоматом К. Совокупность L(K) именуется языком, который способен распознать данный конечный автомат «К». Язык L считается регулярным, если он может быть распознан некоторым конечным автоматом.
Конечный автомат, определяемый выражением:
Может быть удобно задан специальной диаграммой переходов. Диаграмма переходов является ориентированным графом, множество вершин которого совпадает с множеством состояний Q=
На рисунке ниже изображена диаграмма автомата K1, работающего над словами алфавита A=
Рисунок 1. Диаграмма автомата K1. Автор24 — интернет-биржа студенческих работ
Автомат имеет два состояния, q0 и q1, причем «хорошим» считается лишь состояние q1.
Начав работу в состоянии q0, автомат под влиянием символов a, b из этого состояния не может выйти, а под влиянием символа «с» реализуется переход в состояние q1. Далее любой поступающий символ (буква) оставляет автомат в том же состоянии. Это означает, что автомат K1 распознает язык L1, который состоит из слов, имеющих в своем составе букву «с». Этот язык может считаться регулярным.