Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Тема 18.2. Способы задания конечного автомата

Тема 14.1. Граф достижимости | Тема 14.2. Взаимная достижимость, компоненты сильной связности и базы графа | Тема 15.1. Деревья | Тема 15.2. Обход графа | Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости. | Тема 16.1. Формальное описание машины Тьюринга | Тема 16.2. Примеры построения машины Тьюринга | Тема 16.3. Свойства машины Тьюринга как алгоритма | Тема 17.1. Теоретическая часть. Состав машины Поста | Тема 17.2. Применимость программ. Определение результата выполнения программ |


Читайте также:
  1. I. Проверка домашнего задания
  2. II Проверка домашнего задания
  3. II. Проверка домашнего задания.
  4. II. Проверка домашнего задания.
  5. II. Проверка домашнего задания.
  6. II. Способы взрывания
  7. Анализ задания

Комбинационные схемы, хотя и позволяют реализовать любые фиксированные зависимости между входными и выходными сигналами, не могут изменять характера своего поведения (т.е. последовательности обработки данных) – любое такое изменение требует изменения структуры схемы, т.е., по сути, переходу к другой схеме. Решить проблему перестройки работы без изменения структуры схемы возможно, если ввести в неё элементы памяти, которые позволяли бы фиксировать и сохранять промежуточные состояния устройства – в этом случае выходной сигнал будет зависеть не только от входного сигнала, но и от состояния схемы. Если количество таких элементов конечно, то, как указывалось выше, дискретное устройство будет называться конечным автоматом.

Как указывалось ранее, задаёт порядок преобразования входных символов и состояния автомата на предыдущем такте в состояние на последующем, а – преобразования входных символов и состояния автомата на текущем такте в выходной символ. Если – начальное состояние автомата, а – номер такта, то его работа описывается системой:

Данные соотношения получили название системы канонических уравнений конечного автомата. Пользуясь ими можно, начиная с , последовательно находить все последующие состояния автомата и выходные символы.

Выделяются два типа автоматов – инициальные и неинициальные. В инициальных автоматах начальное состояние фиксировано (т.е. они всегда начинают работать из одного и того же состояния ). В неинициальных автоматах в качестве начального состояния может быть выбрано любое из множества ; этим выбором определяется дальнейшее поведение автомата.

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

В табличном способе автоматные функции задаются двумя конечными таблицами, именуемыми соответственно матрицей переходов и матрицей выходов. В этих таблицах строки обозначаются буквами входного алфавита, а столбцы – буквами внутреннего алфавита (символами, кодирующими внутреннее состояние автомата). В матрице переходов на пересечении строки () и столбца () помещаются значения функции , а в матрице выходов – значения функции .

Пример

По заданному табличному представлению автомата построить систему его команд. Пусть конечный автомат имеет алфавиты ={a, b} = {a, b, c}, = {1, 2, 3}, а автоматные функции задаются таблицами:

 

 
           
a       a b a b
b       b c c c

 

Представленные две таблицы можно объединить в одну, условившись в каждую клетку на первую позицию ставить значение , а через запятую на вторую позицию помещать значение . В результате получится следующая «сводная» таблица:

,  
     
a 3,b 3,a 1,b
b 2,c 3,c 3,c

Видно, что таблица стала весьма напоминать таблицу, задающую функциональную схему машины Тьюринга. Из неё легко просматриваются команды преобразования, осуществляемые данным автоматом:

Пусть на начальном такте автомат находится в состоянии = 1 и на его вход в последующие такты подаётся последовательность abb. Пользуясь перечнем команд можно установить, что автомат преобразует эту последовательность в bcc и при этом окажется в состоянии 3.

Другой вариант описания автоматных функций – графический. Он обладает большей наглядностью, чем табличный. Состояния автомата задаётся посредством ориентированного графа, который называется диаграммой (точнее, диаграммой Мура). Вершины графа помечены символами из алфавита состояний автомата , а каждой команде соответствует ребро, идущее из вершины в вершину ; при этом ребру приписывается метка . Таким образом, ребро возникает в том случае, если автомат, находящийся в состоянии , посредством некоторого входного сигнала может быть переведён в состояние . Если такой перевод возможен при нескольких входных воздействиях ,…, , и при этом формируются выходные сигналы ,…, , то ребру приписывается выражение .

Для диаграмм, представляющих конечный автомат, справедливы следующие утверждения:

· из одной вершины не может выходить двух рёбер с одинаковым входным символом (условие однозначности);

· если при работе автомата реализуется входная комбинация , то обязательно существует ребро, идущее из вершины помеченное символом (условие полноты);

· количество вершин и ребер диаграммы является конечным.

Пример

Построить диаграмму для конечного автомата, описанного в предыдущем примере.

Если на начальном такте автомат находился в состоянии = 1 и на его вход в последующие такты подавались символы abb, то, пользуясь диаграммой, можно проследить последовательность преобразований: – выходные символы будут появляться в порядке bcc.


Дата добавления: 2015-10-28; просмотров: 59 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации| Тема 18.3. Эквивалентные автоматы

mybiblioteka.su - 2015-2024 год. (0.009 сек.)