Похожие работы
|
Кафедра высшей математики - страница №6/7
ТЕМА 8 КОНЕЧНЫЕ АВТОМАТЫ8.1 Детерминированные функции8.2 Графическое задание детерминированных функций8.3 Ограниченно-детерминированные функции8.4 Каноническое уравнение ограниченно-детерминированных функций Автоматом называют дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы. Если множество состояний автомата, а также множество входных и выходных сигналов конечны, то автомат называют конечным автоматом. Все реальные автоматы являются конечными. Информацию, поступающую на вход автомата, и преобразующую входную информацию принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит, – буквами, а любые конечные упорядоченные последовательности букв данного алфавита – словами в этом алфавите. Автоматы функционируют в дискретные моменты времени, которые обозначаются натуральными числами t = 0, 1, 2,…. В каждый момент дискретного времени на вход автомата поступает один сигнал (буква), фиксируется определённое состояние автомата и с выхода снимается один сигнал. Реальные автоматы могут иметь, вообще говоря, несколько входов и выходов. В некоторых случаях для решения задач синтеза удобно заменить такие автоматы автоматами с одним входом и одним выходом. Для этого достаточно закодировать соответствующим образом входные и выходные сигналы исходного алфавита. Если, например, автомат имеет два входа, на каждый из которых подаются сигналы 0 или 1, то все возможные комбинации входных сигналов можно закодировать четырьмя буквами (0, 0), (0, 1), (1, 0), (1, 1). Процесс дискретного преобразования информации автоматами можно описать с помощью детерминированных функций. Обозначим через ={0, 1, …, k-1}, где k – некоторое натуральное число, а через множество всех k-значных последовательностей a таких, что а = {a(1), a(2),…,a(t), …}, где a(i) для всех I = 1, 2,… . Обозначим через множество всех функций y = f , определённых на наборах , где и принимающих значение из . Функции из преобразуют наборы k-значных последовательностей в k-значные последовательности. В множество включим также все последовательности из , рассматривая их как функции, зависящие от пустого множества переменных, т. е. как константы. С помощью векторной записи функции от n переменных из можно свести к функции от одной переменной. Обозначим набор переменных через Х, вместо y = f будем писать y = f (Х). При этом значение переменной Х, есть вектор а = компонентами которого являются последовательности из , . Будем рассматривать а как последовательность векторов , где . Таким образом, мы будем считать, что выполняется тождество: = =. Лемма 1 Число наборов , где равно . Итак, функцию y = f с помощью векторной записи можно свести к функции y = , где N =. Таким образом, изучение функции y = f из можно свести к изучению функции от одной переменной из , где N =. Определение 1 Функция y = из называется детерминированной, если каково бы ни было число t и каковы бы ни были последовательности а и b такие, что a(1)=b(1), a(2)=b(2), … a(t)=b(t) значения функций α, β, где α=, β= представляют собой последовательности, у которых тоже совпадают первые t членов, т. е. α(1) = β(1), α(2) = β(2), …, α(t) = = β(t). Множество всех детерминированных функций обозначим через . Из определения детерминированной функции следует, что значение α(t) (α=) зависит только от значения первых t членов входной последовательности а, т. е. а(1), а(2), …, а(t), следовательно α(t)=φ(а(1), а(2), …, а(t)). Приведём примеры как детерминированных, так и недетерминированных функций. Пример 1 Рассмотрим функцию y = , определённую следующим образом Покажем, что данная функция недетерминированная. Действительно, возьмём две входные последовательности и . Тогда и . Следовательно, данная функция недетерминированная. Пример 2 Рассмотрим функцию из , определённую следующим образом .Здесь выходная последовательность – почленная конъюнкция входных последовательностей. Очевидно, что . Пример 3 Рассмотрим функцию z = x + y, осуществляющую сложение 2-значных последовательностей в двоичной системе с бесконечным числом разрядов. Для этого используется обычный алгоритм сложения двух чисел столбиком Очевидно, что z(t) определяется по первым t слагаемых, т. е. x + y. Детерминированная функция может быть проинтерпретирована следующим образом. Пусть мы имеем некоторый «дискретный преобразователь», в котором существует n входов и один выход . И в эти же моменты t на выходе возникает выходная последовательность , причем . Очевидно, что в дискретном преобразователе значения α(t) зависит только от значений входных последовательностей в момент времени 1,2,…,t и не зависит от значений в будущие моменты времени. Поэтому преобразование есть детерминированная функция. 8.2 Графическое задание детерминированных функций Пусть . Выше мы показали, что с помощью векторной записи данную функцию можно свести к функции , где . Рассмотрим бесконечную фигуру (рисунок 1):
Рисунок 1 Называть её будем деревом, и построена она следующим образом. Возьмём произвольную вершину , которую назовём корнем дерева. Из неё проведём N рёбер, которые образуют первый ярус. Из концов каждого из рёбер также проведём N рёбер, которые образуют второй ярус и т. д. Рёбра каждого пучка нумеруются слева направо числами 0, 1,…, N-1 или их значениями в k-ичной системе счисления. В дальнейшем на рисунках номера рёбер будут опускаться. Далее, каждому ребру в построенном дереве произвольным образом припишем одно из чисел множества {0, 1,…, k-1}. В результате получим так называемое нагруженное дерево. Рассмотрим следующее нагруженное дерево (рисунок 2): Рисунок 2 Начиная движение с корня дерева, пойдём по рёбрам. Так, например, последовательности (0, 0, 1, 1…), где числа 0, 0, 1, 1, … – номера рёбер, соответственно, 1-го,2-го,3-го,4-го и т. д. ярусов соответствует выделенный маршрут и последовательность (0, 1, 1, 1…). Ясно, что маршруты в нагруженном дереве, соответствующие данным последовательностям на первых t ярусах совпадают. А это значит, что , т. е. функция детерминированная. Обратное утверждение очевидно. Теорема доказана. Рассмотрим следующие примеры: . . . . . . . . . . 1 0 1 0 1 0 1 0 1 0 1 0 Рисунок 3 Например, входной последовательности {0, 1, 1, …} будет соответствовать входная последовательность {1, 0, 0, …}. Для данной функции k=n=2 и число ребер, выходящих из вершин равно N = = 4. Ребру с номером D = (0,0) соответствует значение (0,0) = 0 1 = (0,1) 0·1 = 0 2 = (1,0) 1·0 = 0 3 = (1,1) 1·1 = 1. Следовательно, данной функции соответствует следующее нагруженное дерево (рисунок 4): Рисунок 4 Пример 6 , k = n = 1, N = = 1. Дерево, соответствующее данной функции строится следующим образом. Процесс приписывания ребрам чисел начинается с 1-го яруса 0 = (0,0) 0+0=0 1 = (0,1) 0+1=1 2 = (1,0) 1+0=1 3 = (1,1) 1+1=0 При этом, если появляется перенос в следующий разряд, то конец соответствующего ребра кончается кружочком. Это позволяет выполнить вычисление в следующем ярусе (рисунок 5): Рисунок 5 8.3 Ограниченно-детерминированные функции Возьмем нагруженное дерево для некоторой детерминированной функции . Пусть – произвольная его вершина -го яруса. Данную вершину можно рассматривать как корень нагруженного дерева. Согласно теореме 1 оно определяет некоторую детерминированную функцию . Определение 2 Два поддерева с корнями и исходного дерева называются эквивалентными, если . Очевидно, что при естественном наложении двух эквивалентных поддеревьев их нумерации совпадают. Так, в дереве (рис.3 и рис.4) все поддеревья эквивалентны, а в дереве (рис.5) поддеревья с корнями эквивалентны, а с корнями и не эквивалентны. Определение 3 Весом дерева и весом соответствующей детерминированной функции называется максимальное число попарно неэквивалентных поддеревьев. Например, все функции из примеров 4, 5 равны 1, а из примера 6 равны 2. Определение 4 Детерминированная функция называется ограниченно – детерминированной функцией, если она имеет конечный вес. Класс всех ограниченно – детерминированных функций обозначим через Функции из примеров 4, 5, 6 являются ограниченно-детерминирован- ными функциями. Рассмотрим следующую детерминированную функцию. Пример 7 . Ясно, что вес данной функции , т. е. она не является ограниченно-детерминированной. Пусть , вес которой равен r. Рассмотрим алфавит , который назовём внутренним алфавитом. Каждой вершине нагруженного дерева, соответствующей функции припишем одну из букв алфавита с соблюдением следующего правила: эквивалентным вершинам приписываются одни и те же буквы из . В результате получаем так называемое полное нагруженное дерево. Для любой ограниченно – детерминированной функции соответствующее ей полное нагруженное дерево можно свести к конечному дереву с занумерованными ребрами и вершинами. Если в нем провести отождествление эквивалентных вершин, то получим так называемую диаграмму Мура. В ней нулём отмечена начальная вершина и ребрам приписаны пары чисел (a, b), первое из которых обозначает номер ребра, а второе, чем данное ребро нагружено. Так функция соответствует диаграмме Мура. А функция 8.4 Каноническое уравнение ограниченно-детерминированных функций Пусть – ограниченно-детерминированная функция с весом r. Пусть – входная последовательность. Ей соответствует выходная последовательность и последовательность состояний . Возьмем другую входную последовательность . Ей соответствуют, выходная последовательность и последовательность состояний В общем случае из того, что не следует, что . Однако, если и , то и . Другими словами это означает, что если два одноименных ребра () выходят из эквивалентных вершин (), то они будут нагружены одной и той же буквой () и будут входить в эквивалентные вершины (). Это означает, что (8.1) Уравнения (8.1) называются каноническими уравнениями функции . Первое уравнение называется уравнением выход, второе уравнением перехода. Уравнения (8.1) можно задать с помощью канонической таблицы.
Пусть x(t) и y(t) из {0,1}, а . Если вес r ≤ 2, то каноническая таблица есть таблица истинности. Если r > 2, то каноническая таблица не является таблицей истинности. Но с помощью кодирования всех чисел алфавита в двоичной системе счисления мы её можем преобразовать в таблицу истинности. Рассмотрим теперь функцию от n переменных с весом r > 1, – внутренний алфавит. Закодируем все числа из алфавита в двоичной системе счисления наборами из {0,1} длинной . В этом случае канонические уравнения искомой функции имеют вид: В дальнейшем договоримся, что начальные состояния в канонических уравнениях (8.2) q(0) = 0, а в уравнениях (8.1) . Пример 8 Найти канонические уравнения функции Ранее мы показали, что вес данных функций равен 2 и её диаграмма Мура Построим каноническую таблицу.
Данная каноническая таблица является таблицей истинности. Запишем канонические уравнения, используя результаты темы 3. Используя законы алгебры логики: Пример 9 Найти каноническое уравнение для функции заданной следующей диаграммой Мура Строим каноническую таблицу.
Отсюда Заметим, что если вес функции равен 1, то в канонических уравнениях будет отсутствовать. Ясно, что вес данной функции равен 3. Построим каноническую таблицу для данной функции:
Данная таблица не является таблицей истинности. Преобразуем данную таблицу в таблицу истинности. Для этого значения второго и четвёртого столбца закодируем в двоичной системе счисления:
Доопределим данную функцию следующим образом:
Составим канонические уравнения, используя аппарат булевой алгебры: 1) y(t)= = =; ; Итак, искомые канонические уравнения имеют вид: Каждой ограниченно-детерминированной функции можно сопоставить канонические уравнения. Однако выбор канонических уравнений не однозначен. Эта неоднозначность связана: 1) с различными способами кодирования состояний; 2) с различными способами доопределения функций. Очевидно, что канонические уравнения позволяют вычислить по входной последовательности a={a(1),a(2),…,a(t),…} выходную последовательность b={b(1),b(2),…,b(t),…}. Итак, для задания конечного автомата фиксируется три конечных множества (алфавита): – множество возможных входных сигналов ; – множество возможных выходных сигналов ; – множество возможных внутренних состояний автомата . На этих множествах задаются две детерминированные функции: – функция переходов Ψ, определяющая состояние автомата q(t) дискретного времени t в зависимости от состояния автомата q(t-1) и значения входного сигнала в момент времени t: q(t)= Ψ(x(t),q(t-1)); – функция выходов Ф, определяющая зависимость выходного сигнала автомата y(t) от состояния автомата q(t-1) и входного сигнала x(t) в момент времени t: y(t)=Ф(x(t),q(t-1)). Кроме того, на множестве состояний автомата фиксируется одно из внутренних состояний q(0) в качестве начального состояния. 1 Дайте определение детерминированной функции. 2 Приведите примеры детерминированных функций. 3 Приведите примеры недетерминированных функций. 4 Приведите графическую интерпретацию детерминированных функций. 5 Что такое бесконечное нагруженное дерево? 6 Что такое вес бесконечно нагруженного дерева? 7 Какие функции называются ограниченно-детерминированными? 8 Приведите примеры ограниченно-детерминированных функций. 9 Приведите примеры неограниченно-детерминированных функций. 10 Что такое диаграмма Мура? 11 Дайте определение канонических уравнений ограниченно-детерми- нированных функций. |
|