Презентация на тему "Абстрактный автомат. Описание автомата"

Содержание

• 
  Слайд 1

  Тема 2. Абстрактный автомат

  Лекция 3 Описание автомата

• 
  Слайд 2

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

  2 Существуют два способа задания автомата: Табличный Графовый Автоматы удобно описывать с помощью таблиц, а для наглядности использовать графы

• 
  Слайд 3

  Табличный способ (1)

  При табличном описании задают две таблицы, одна из которых раскрывает функцию переходов (см. таблицу 1.1), а другая - функцию выходов (см. таблицу 1.2) Число строк таблиц m равно числу состояний автомата, т.е. m = |Q| Число столбцов таблиц n равно числусимволов входного алфавита, т.е. n = |X| В позиции первой таблицы записываютзначения очередных состояний автомата q[τ+1]∈Q, в которые он переходит длякаждой пары (q[τ], x[τ])∈(Q•X) В позиции второй таблицы записывают значениясимволов выходного алфавита y[τ]∈Y, которые генерирует автомат для каждойпары (q[τ], x[τ])∈(Q•X) Если в таблицах 1 и 2 определены значения q[τ+1]∈Q и y[τ]∈Y для каждой пары (q[τ], x[τ])∈(Q•X), то есть заполнены все позиции таблиц,то дано описание детерминированного автомата

• 
  Слайд 4

  Табличный способ (2)

  Обычно эти таблицы совмещают в одну, которая раскрывает операторповедения (ψ,ϕ): (Q•X) → (Q•Y) (см. таблицу 1.3) В позициях этой таблицызаписывают пары (q[τ+1], y[τ]) для каждой пары (q[τ], x[τ]) Таблица 1.1 – Функция переходов Таблица 1.2 – Функция выходов

• 
  Слайд 5

  Табличный способ (3)

  Таблицы абстрактного автомата совпадают с таблицами автомата Мили Поэтому таблица 1.3 описывает поведение автомата Мили Таблица автомата Мура(табл.1.4) несколько отличается от таблицы автомата Мили, так как ϕ:Q→Y.Значение выходного символа приписывают, как метку, состоянию автомата Описание С-автомата есть объединение таблиц 1.3 и 1.4. Так как в таблицах 1.3 и1.4 определены все позиции, то такими таблицами дано описаниедетерминированных автоматов Таблица 1.3 Таблица 1.4

• 
  Слайд 6
  

  Табличный способ (4): задание абстрактного недетерминированного автомата

  В практике проектирования автоматов встречаются случаи, когда функции переходов и/или выходов не определены для некоторых значений символов входного алфавита. В этом случае говорят, что автомат недетерминированный или частично определенный При описании таких автоматов неопределенные позиции таблиц помечаются символом "*" В таблицах 1.5, 1.6, 1.7 и 1.8 приведено описание недетерминированных автоматов Таблица 1.1 – Функция переходов Таблица 1.2 – Функция выходов

• 
  Слайд 7
  

  Табличный способ (5): задание недетерминированных автоматов Мили и Мура

  Таблица 1.7 Таблица 1.8

• 
  Слайд 8

  Задание автомата графом: определение таблиц соединения состояний

  Поведение автомата удобно анализировать с помощью графов, вершинами которого являются элементы множества q∈Q, тогда вершина-исток есть образ текущего состояния q[τ] вершина-сток - образ очередного состояния q[τ+1] дуги отображают переход автомата из одного состояния в другое (q[τ], q[τ+1]) под воздействием x[τ]∈X Для описания автомата с помощью графов удобно воспользоваться таблицами соединений состояний автомата Строки и столбцы такой таблицы представляют символы q∈Q Число строк и столбцов таблицы равно m Строки этой таблицы характеризуют текущее состояние, т.е. q[τ], а столбцы - очередное, т.е. q[τ+1] Позиции таблицы заполняют значениями пары (x[τ]/y[τ]) для соответствующего перехода автомата из текущего состояния в очередное

• 
  Слайд 9

  Задание автомата графом: таблицы соединения состояний

  Таблицей 1.9 дано описание соединений состояний автомата Мили Таблицей 1.10 - автомата Мура Для автомата Мили на дугах графа указывают пару (входной символ/выходной символ) Для автомата Мура на дугах графа указывают только входной символ, определяющий переход автомата из одного состояния в другое, а выходной символ y, приписывают к каждой вершине графа Таблица 1.9 Таблица 1.10

• 
  Слайд 10

  Задание автомата графом: условия использования

  При начертании графа детерминированного автомата следует соблюдать следующие условия: для каждого символа x∈X есть дуга, исходящая из вершины q∈Q каждый символ x∈X у каждой вершины-истока q∈Q принадлежит только одной дуге если между двумя вершинами q∈Q существует несколько дуг, что может быть обусловлено переходом автомата из состояния qs∈Q в состояние qt∈Q при различных символах на входе, то есть xi ≠xj, то эти дуги могут быть заменены одной дугой с указанием дизъюнктивной связи этих состояний например если yu≠yv, то на дуге следует указать (xi/yu ∨ xj/ yv) если yu=yv=y, то - (xi∨xj)/y)

• 
  Слайд 11

  Контрольные вопросы

  Объясните таблицы переходов, выхода, поведения и соединения состоянийдетерминированного автомата Мили Объясните таблицы переходов, выхода, поведения и соединения состоянийдетерминированного автомата Мура Объясните таблицы переходов, выхода, поведения и соединения состоянийнедетерминированного автомата Мили Объясните таблицы переходов, выхода, поведения и соединения состоянийнедетерминированного автомата Мура Описать автомат М с алфавитом X=Y={0,1}, который, исходя из начальногосостояния q0, перерабатывает входную последовательность α в задержаннуюна два такта последовательность β=(00α) Описать автомат М с двумя состояниями, который переводит десятичныецифры 0,1, …,9 поданные на вход, в двоичные последовательности0000,0001, …,1001 соответственно, а двоичные последовательности0000,0001, …,1111, в десятичные записи 0,1, …,15 соответственно Описать автомат М с алфавитом X=Y={0,1}, который печатает на выходе '1',если непосредственно перед этим он считал четыре '1' последовательно, впротивном случае печатает "0". Автомат работает до тех пор, пока не считаеттри "0" последовательно, после чего печатает лишь '0'