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

Глава 2. Способы задания конечных автоматов

Читайте также:
  1. I. Способы удерживания шеста
  2. Алгоритм действий при выполнении задания
  3. Алгоритм действий при выполнении задания
  4. АНАЛИЗ КОНЕЧНЫХ АВТОМАТОВ. (до90 минут)
  5. Веселые задания
  6. Виды административно-правовых норм и способы их реализации.
  7. Виды хирургических швов и способы их наложения.

Можно по-разному описывать принципы работы автомата. Один из способов описания - с помощью набора правил функционирования - использовался в примере 1 §1. Рассмотрим более удобный табличный способ. Чтобы задать автомат табличным способом, надо заполнить его таблицу выходов и переходов, исходя из функции выходов f и функции переходов g (табл. 1).

Таблица 1

  v1 vr
a1 f(a1,v1),g(a1,v1) f(a1,vr),g(a1,vr)
   
аs f(as,v1),g(as,v1) f(as,vr),g(as,vr)

 

В крайнем левом столбце таблицы перечислены символы входного алфавита A = {a12, ...,as}, а в верхней строке - элементы множества состояний V= {v1,v2,...,vr}. В клетке, стоящей на пересечении строки аi и столбца vj, стоит пара f(ai,vj), g(ai,vj), которая согласно определению функций f и g указывает, что если автомат находился в состоянии vj и на вход ему подали сигнал ai, то на выходе автомата получим сигнал f(ai,vj), и автомат перейдет в состояние g(ai,vj). Используя такую таблицу, можно для любой последовательности входных сигналов определить, как будет выглядеть соответствующая последовательность выходных сигналов или состояний автомата.

Обычно во множестве V={v1,v2,…,vr} особо выделяют одно из состояний (как правило, это состояние v1) и называют его начальным. Этот факт записывают в виде равенства q(0)=v1 и считают, что в момент «включения» автомата его состояние (точнее, состояние его памяти) известно. Такой автомат называется инициальным. В дальнейшем мы будем рассматривать только инициальные автоматы.

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

Пример 1. Пусть автомат, алфавиты которого A = В = {а, b, с }, задан с помощью таблицы выходов и переходов (табл. 2). Будем считать его инициальным автоматом с начальным состоянием v1.

Таблица 2

  v1 v2
а а, v1 а, v2
b b, v1 а, v1
с c, v2 c, v2

Предположим, что ему на вход могут поступать последовательности символов (символьные строки) произвольной длины, но только двух типов - оканчивающиеся символом b или символом с. Тогда, зная состояние автомата после завершения его работы над входной строкой, но не имея доступа к этой строке, мы, тем не менее, можем точно установить её тип. Действительно, из табл. 2 видно, что когда на вход автомату поступает символ b, то он из любого состояния переходит в состояние v1. Значит, в этом состоянии автомат и завершит работу, если символ b был последним символом входной строки. Аналогично из табл. 2 следует, что если на вход автомату подать символ с, то он из любого состояния перейдет в состояние v2 и в нем же остановится, если входная строка оканчивается символом с. Но поскольку мы знаем, что последний символ входной строки - это всегда либо b, либо с, то само состояние, в котором автомат завершит свою работу, покажет нам тип входной строки: когда автомат завершает работу в состоянии v1 это означает, что входная строка заканчивалась символом b. Если же автомат остановился в состоянии v2, то она заканчивалась символом с.

Предположим, например, что входные строки - это идентификаторы переменных и констант в некотором языке программирования. И пусть согласно синтаксису этого языка имя переменной - это символьная строка в алфавите A = {а, b, с }, которая всегда заканчивается символом b, а имя константы - строка, заканчивающаяся символом с. Проведенный выше анализ показывает, что данный автомат отличает имя константы от имени переменной. Значит, он способен выполнять одну из функций компилятора - осуществлять синтаксический анализ символьных строк, подаваемых ему на вход. Заметим, что рассмотренный автомат - это автомат из примера 1 §1, у которого символы алфавитов A и В переобозначили по следующему правилу: а1=b1= а, а2 = b2 = b, а3 = b3 = с.

Другой способ задания автомата - с помощью диаграммы Мура. При таком способе автомат изображается в виде ориентированного графа, в котором допускаются кратные дуги и петли. Число вершин равно r — числу состояний автомата. Каждая вершина помечена символом из множества состояний V = { v1 , v2 ,... vr }. Дуга выходит из вершины vk в вершину vn тогда и только тогда, когда в данном автомате возможен переход из состояния vk в состояние vn по некоторому входному сигналу. Все дуги, выходящие из вершины vk, помечены парой символов вида (ai,bj), где аi ÎA, bj=f(ai,vk). Иными словами, начало дуги определяет состояние автомата в предшествующий, а её конец - в последующий моменты времени. При этом на самой дуге указывается входной и соответствующий ему выходной сигналы.

Граф диаграммы Мура должен удовлетворять условию детерминированности. Оно заключается в том, что для любого входного символа аi из каждой вершины должна выходить только одна дуга, помеченная этим символом. Поэтому в диаграмме Мура из каждой вершины выходит ровно s дуг, где s - это мощность алфавита А. Диаграмма Мура для автомата, рассмотренного в примере 1, изображена на рис. 2.

 
 

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

Простейшим детерминированным автоматом с n входами и m выходами является схема из функциональных элементов, реализующая систему m булевых функций от n аргументов. Это пример логического автомата, у которого отсутствует блок памяти.

Автомат, имеющий много входных каналов, как и автомат с одним входом, можно задавать и табличным способом, и диаграммой Мура. В этом случае таблица выходов и переходов в крайнем левом столбце содержит не отдельные символы входного алфавита, а все возможные наборы входных символов длины n, где n - число входных каналов. Аналогичные изменения будут и в диаграмме Мура: первый элемент метки на дугах теперь представляет собой не отдельный сим­вол алфавита A, а один из возможных наборов входных символов длины n. Рассмотрим соответствующий пример.

Пример 2. Пусть автомат задан диаграммой Мура (рис. 3).

 

 
 

Рис.3

Он имеет два состояния v1 и v2, из которых v1 считается начальным. Входной и выходной алфавиты А и В совпадают, причем А = В = {0,1}. Метки на дугах указывают, что у автомата два входных и один выходной канал. Например, метка (01,1) на дуге, ведущей из вершины v1 в v1 , означает, что если в начале такта автомат находился в состоянии v1 и по первому каналу на вход ему поступил сигнал 0, а по второму каналу 1, то на его выход будет направлен сигнал 1, и в конце такта автомат останется в том же состоянии v1.

 
 

Данный автомат можно было бы задать таблицей выходов и переходов (табл. 15). Покажем, что он складывает по модулю 2n два произвольных n -разрядных числа a=(an,an-1,…,a1) и b=(bn,bn-1,…,b1), заданных в двоичной системе счисления, и выдает результат c=(cn,cn-1,…,c1) также в двоичной системе счисления. Числа а и b будем подавать на вход автомата поразрядно, начиная с младших разрядов, т.е. в моменты времени t = 1, 2, 3,...,n по первому входному каналу будет поступать сигнал аt, а по второму каналу bt. Тогда в конце i -го такта на выходе автомата появится сигнал сt. Анализ табл. 3 показывает, что входные сигналы аt, bt, и соответствующий выходной сигнал сt связаны равенст­вом

 

где dt = 0, если в начале i -го такта автомат находится в состоянии v1 , либо dt=1, если автомат находится в состоянии v2. По смыслу величи­на dt является признаком переноса единицы в следующий разряд и оп­ределяется только состоянием автомата в начале t -го такта. Поскольку в начальный момент времени автомат находится в состоянии v1 то d1 = 0. Таким образом, данный автомат заn тактов выполнит сложение по модулю 2n чисела и b «столбиком» и выдаст их сумму поразрядно, начиная с младшего разряда.

 


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



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