22116

Способы задания автомата

Лекция

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

Существует несколько способов задания работы автомата но наиболее часто используются табличный и графический. Совмещенная таблица переходов и выходов автомата Мили: xj ai a0 an x1 a0x1 a0x1 anx1 anx1 xm a0xm a0xm anxm anxm Задание таблиц переходов и выходов полностью описывает работу конечного автомата поскольку задаются не только сами функции переходов и выходов но и также все три алфавита: входной выходной и алфавит состояний. Для задания автомата Мура требуется одна таблица поскольку в этом...

Русский

2013-08-04

362 KB

20 чел.

Лекция 2

Способы задания автомата

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, , } , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов и выходов . При этом среди множества A = {a0,a1,…, an} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

  1.  Табличный способ. При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Таблица переходов

xj\aj

a0

an

x1

(a0,x1)

( an,x1)

xm

( a0,xm)

( an,xm)

Таблица выходов

xj\aj

a0

an

x1

(a0,x1)

( an,x1)

xm

( a0,xm)

( an,xm)


Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = [ ai,xj], в которое автомат перейдет из состояния ai под воздействием сигнала xj; а в таблице выходов – соответствующий этому переходу выходной сигнал yg = [ ai,xj].

Совмещенная таблица переходов и выходов автомата Мили:

xj\ai

a0

an

x1

(a0,x1)/ (a0,x1)

(an,x1)/ (an,x1)

xm

(a0,xm)/ (a0,xm)

(an,xm)/ (an,xm)

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

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

Отмеченная таблица переходов автомата Мура:

yg

(a0)

(an)

xj\ac

a0

an

x1

(a0,x1)

(an,x1)

xm

(a0,xm)

(an,xm)

Автомат Мили     Автомат Мура

В этой таблице каждому столбцу приписан, кроме состояния ai, еще и выходной сигнал y(t) = (a(t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.

Приведем примеры табличного задания автоматов Мили и Мура:

По этим таблицам можно найти реакцию автомата на любое входное слово. Например.

Для автомата Мили:   Для автомата Мура:

x1x2x2x2x1…    x1x2x2x2x1

a0a1a0a0a0a1     a0a2a4a1a4

y1y1y2y2y1     y2y1y2y1y2

  1.  Графический способ задания автомата (задание автомата с помощью графа).

Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as, если в автомате имеется переход из ai в as, т.е. as =  (ai, xj). В автомате Мили дуга отмечается входным сигналом xj, вызвавшим переход, и выходным сигналом yg, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

а)      б)


 

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

75681. Стилистическое использование различных типов сложного предложения 88.91 KB
  Не останавливаясь подробно на синтаксисе устной формы разговорной речи отметим что при письменном ее отражении в художественных текстах и прежде всего в драматургии наиболее широко используются бессоюзные сложные предложения. Попробуем предикативные единицы объединенные в сложные бессоюзные предложения в цитированном отрывке связать с помощью союзов: Думаю что ничего у нас не выйдет. У него дела много так что ему не до меня поэтому и внимания не обращает. Из этого конечно не следует что в художественной речи отражающей...
75682. Стилистическая оценка параллельных синтаксических конструкций 127.53 KB
  Редактор прочитал рукопись и написал рабочую рецензию. Редактор прочитав рукопись написал рабочую рецензию. Редактор прочитавший рукопись написал рабочую рецензию. Редактор закончил чтение рукописи и приступил к написанию рабочей рецензии.
75683. Стилистическая оценка заимствованных слов 118.35 KB
  Заимствования из древних языков греческого латинского тюркизмы галлицизмы слова из голландского немецкого английского полонизмы украинизмы и др. В средствах массовой информации полюбили слова популизм популист используя их однако совсем не так как это принято на Западе. Примеров такого толкования слова можно привести множество вот один из них: . Словари иностранных слов не успевают освоить новые заимствования поэтому читатель не владеющий английским нередко оказывается беспомощным встречая непонятные слова в газетах...
75684. Лексические образные средства 219.96 KB
  Понятие образности речи Слова образность образный используются в стилистике в разных значениях. Образность в широком смысле этого слова как живость наглядность красочность изображения неотъемлемый признак всякого вида искусства форма осознания действительности с позиций какого-то эстетического идеала образность речи частное ее проявление. Стилистика рассматривает образность речи как особую стилевую черту которая получает наиболее полное выражение в языке художественной литературы. Более узкое понимание образности речи основано...
75685. Фоника. Понятие фоники. Значение звуковой организации речи 365.48 KB
  Понятие фоники Фоника раздел стилистики изучающий звуковую сторону речи. В отличие от фонетики представляющей собой раздел языкознания который изучает способы образования и акустические свойства звуков того или иного языка фоника наука об искусстве звуковой организации речи. Под фоникой понимают также звуковую организацию речи т. При этом говорят о фонике того или иного произведения исследуя например фонику поэмы стихотворения анализируя эстетическую функцию различных фонетических средств прежде всегозвуков речи.
75686. СТИЛИСТИКА СЛОВООБРАЗОВАНИЯ 189.65 KB
  Русский язык отличается исключительным богатством словообразовательных ресурсов, обладающих яркой стилистической окраской. Это обусловлено развитой системой русского словообразования, продуктивностью оценочных суффиксов, придающих словам разнообразные экспрессивные оттенки
75687. Стилистика имени числительного 164.35 KB
  Однако этот графический способ обозначения числа количества здесь уже не является единственным: параллельно могут быть использованы и словесные обозначения чисел количества что открывает пути к функционально-стилевому применению числительных.
75688. Стилистика местоимения. Употребление местоимений в разных стилях речи 158.67 KB
  Употребление местоимений в разных стилях речи При функционально-стилевой характеристике местоимений прежде всего обращает на себя внимание их особая употребительность в разговорной речи. В разговорной речи употребление местоимений сопровождается различными приемами их актуализации; ср. плеонастическое употребление местоимений при указании на субъект действия: Дима он не подведет или конструкции типа: Так оно и было; Идет она прическа платье все у нее по моде. Использование местоимений в разговорном стиле отличает также свойственная...
75689. Стилистическое использование грамматических форм имен прилагательных 117.66 KB
  Однако при субстантивации прилагательных их грамматические формы преображаются. В числе их немало экспрессивных прилагательных по своей семантике тяготеющих к эмоциональной речи что позволяет вводить их в поэзию: Несказанное синее нежное. Употребление прилагательных в значении существительных добавляет к их лексическому наполнению предметность и образность а форма среднего рода придает оттенок отвлеченности нередко создающей впечатление чего-то неуловимого не вполне осознанного: И повеяло степным луговым цветным из журн.