Конечные автоматы способы задания и основные свойства. Определение и способы задания конечного автомата

Основные определения n Конечным автоматом называется система M ={А, B, S, y}, в которой n n n А = {а 1, . . . , am} – конечный входной алфавит, B ={b 1, . . . , bk} - конечный выходной алфавит, S ={s 1, . . . , sn} - конечный алфавит состояний, : А S S - функция переходов, y: А S B - функция выходов. n Если в автомате M выделено одно состояние, называемое начальным (обычно будет считаться, что это s 1), то полученный автомат называется инициальным и обозначается (M, s 1). n Существует два способа задания автомата: Автоматная таблица, диаграмма переходов

Автоматная таблица n 1) 2) 3) 4) Пример: задать автомат для чтения слова « 001» , если на вход подаются символы « 0» и « 1» . Входной алфавит A={0, 1} Выходной алфавит A={Y, N} Алфавит состояний S={s 0 «» , s 1 « 0» , s 2 « 00» s 3 « 001» } Автоматная таблица двумя способами. задается 1) Строки – состояния автомата. Столбцы – входные символы. На пересечении строк и столбцов указываются функций, y. 2) S, A, y задаются по столбцам. Упр 25 Построить автомат для поиска слова КАКАДУ SA 0 1 S 0 «» S 1, N S 0, N S 1 « 0» S 2, N S 0, N S 2 « 00» S 2, N S 3, Y S 3 « 001» S 1, N S 0, N S Вх y S 0 0 S 1 N 1 S 0 N 0 S 2 N 1 S 3 Y 0 S 1 N 1 S 0 N S 1 S 2 S 3

Диаграмма переходов n Ориентированный называемый графом диаграммой переходов мультиграф, переходов или графа соответствуют состояниям. Если (Si, aj)=Sk, y(Si, aj)=bl, то из вершины Si в вершину Sk веден дуга на которой написано (aj, bl) n В каждой вершине si условиями корректности: 0 1 S 0 «» S 1, N S 0, N S 1 « 0» n Вершины, y S 2, N S 0, N S 2 « 00» S 2, N S 3, Y S 3 « 001» S 1, N S 0, N 1, N выполнены 1) для любой входной буквы aj имеется дуга, выходящая из si, на которой написано aj (условие полноты); 2) любая буква aj, встречается только на одном ребре, выходящем из si (условие непротиворечивости или детерминированности) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y) S 3

Автоматы и входные слова n Для данного автомата M его функции M и y. M могут быть определены не только на множестве А всех входных букв, но и на множестве А* всех входных слов. n Для любого входного слова = aj 1 aj 2. . . ajk (si, aj 1 aj 2. . . ajk) = ((… (si, aj 1), aj 2), . . . , ajk-1), ajk). y (si, aj 1 aj 2. . . ajk) = y((… (si, aj 1), aj 2), . . . , ajk-1), ajk).

Пример: Автоматы и входные слова Пример: = 0101 (S 1, 0101) = ((S 1, 0), 1) (S 1, 0101) = (((S 2, 1), 0), 1) (S 1, 0101) = ((S 3, 0), 1) (S 1, 0101) = (S 1, 1) (S 1, 0101) = S 0 0 1 S 0 «» S 1, N S 0, N S 1 « 0» S 2, N S 0, N S 2 « 00» y(S 1, 0101) = y((((S 1, 0), 1) y(S 1, 0101) = y(((S 2, 1), 0), 1) y(S 1, 0101) = y((S 3, 0), 1) y(S 1, 0101) = y(S 1, 1) y(S 1, 0101) = N , y S 2, N S 3, Y S 3 « 001» S 1, N S 0, N

Автоматное отображение n Зафиксируем в M начальное состояние S 0 и каждому входному слову = a 1 a 2. . . ak поставим в соответствие слово в выходном алфавите: = y (S 0, a 1) y(S 0, a 1 a 2). . . y(S 0, a 1. . . ak). (3 a) n Это соответствие, отображающее входные слова в выходные слова, отображением называется автоматным n Если результатом применения оператора к слову является выходное слово, то это будем обозначать соответственно M() = .

Пример: Автоматное отображение Входному слову = 0101 поставим в соответствие слово в выходном алфавите: = y (S 0, 0) y(S 0, 01)y(S 0, 0101). y (S 0, 0)= N , y 0 S 0 «» S 1, N S 0, N S 1 « 0» S 2, N S 0, N S 2 « 00» S 2, N S 3, Y 1 S 3 « 001» S 1, N S 0, N y(S 0, 01) = y((S 0, 0), 1) = y(S 1, 1) = N y(S 0, 010) = y(((S 0, 0), 1), 0) = y((S 1, 1), 0) = y(S 0, 0)=N y(S 0, 0101) = y((((S 0, 0), 1) =y(((S 1, 1), 0), 1) = = y((S 0, 0), 1) = y(S 0, 1) = NNNN

Свойства автоматного отображения 1) слова и = M() имеют одинаковую длину: | | = | | (свойство сохранения длины); 2) если = 1 2 и M(1 2) = 1 2, где | 1| = | 1|, то M(1) = 1; иначе говоря, образ отрезка длины i равен отрезку образа той же длины.

Виды автоматов n Общая модель конечного автомата (S-конечно), которая рассматривалась ранее, называется автоматом Мили. n Автомат называется автономным, если его входной алфавит состоит из одной буквы: А={а}. Все входные слова автономного автомата имеют вид аа. . . а. n Конечный автомат называется автоматом Мура, если его функция выходов зависит только от состояний, т. е. для любых s, ai, aj y(s, ai) = y(s, aj). Функция выходов автомата Мура естественно одноаргументная; обычно ее обозначают буквой и называют функцией отметок. В графе автомата Мура выход пишется не на ребрах, а при вершине.

Автоматы Мура n Теорема: Для любого автомата Мили существует эквивалентный ему автомат Мура. n При исследовании возможностей автоматов достаточно пользоваться автоматами Мура. Это удобно потому, что автомат Мура можно рассматривать как автомат без выходов, состояния которого различным образом отмечены.

Пример автономного автомата SA а S 1 S 3, 0 S 2 S 4, 0 S 3 S 4, 0 S 4 S 7, 0 S 5 S 4, 2 S 6 S 5, 0 S 7 S 6, 1 S 8 S 9, 0 S 9, 1 S S S S S A={a}, B={0, 1, 2}, S={S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S 9}

Неотличимые состояния n Пусть M и Т - два автомата с одинаковыми входным и выходным алфавитами. Состояние s автомата M и состояние r автомата Т называются неотличимыми, если для любого входного слова M(s,) = T(r,). n Автоматы M и Т называются неотличимыми, если для любого состояния s автомата M найдется неотличимое от него состояние r автомата Т и, наоборот, для любого r из Т найдется неотличимое от него s из M. n Неотличимые состояния называются эквивалентными

Минимальный автомат n Переход от автомата M к эквивалентному автомату называется эквивалентным преобразованием автомата M. n Можно ставить различные задачи о поиске автоматов, эквивалентных данному и обладающих заданными свойствами. Наиболее изученной среди таких задач является задача о минимизации числа состояний автомата: среди автоматов, эквивалентных M, найти автомат с наименьшим числом состояний - минимальный автомат.

Аспекта «работы» автоматов n Можно выделить два основных аспекта «работы» автоматов: 1) автоматы распознают входные слова, т. е. отвечают на вопрос, принадлежит ли поданное на вход слово данному множеству (это автоматыраспознаватели); 2) автоматы преобразуют входные слова в выходные, т. е. реализуют автоматные отображения (автоматы-преобразователи).

ТА в рамках метаматематики n Предмет теории алгоритмов и формальных систем в рамках метаматематики - какие объекты и действия над ними следует считать точно определенными, какими свойствами и возможностями обладают комбинации элементарных действий, что можно и чего нельзя сделать с их помощью. n Главное приложение теории алгоритмов - доказательство невозможности алгоритмического (т. е. точного и однозначного) решения некоторых математических проблем.

Алгоритм n Алгоритм - предписание, однозначно задающее процесс преобразования исходных данных к требуемому результату n Сам процесс преобразования состоит из элементарных дискретных шагов, применение которых конечного число раз приводит к результату

Основные типы алгоритмов n Теория алгоритмов – это метатеория, изучающая различные (качественные и количественные) свойства алгоритмов. n Для исследования качественных свойств определены 3 основных типа алгоритмов: 1) Рекурсивные функции 2) Машина Тьюринга 3) Канонические системы Поста и нормальные алгоритмы Маркова.

Простейшие рекурсивные функции n S 1(x) = x+1 - функция зависит от одной переменной х, и равна х+1. n On(x 1…xn) =0 - функция зависящая от n переменных и всегда равна 0. n Imn(x 1…xn) = xm - функция зависящая от n переменных и всегда равна значению переменной xm

Примитивная рекурсия n Функция f(x 1…xn+1) получаема алгоритмом примитивной рекурсии из функций g(x 1…xn) и h(x 1…xn+2), если f(x 1, …xn, 0) = g(x 1, …xn) (1) f(x 1, …xn, y+1) = h(z), где z=f(x 1, …xn, y) (2) Функция f называется примитивно-рекурсивной, если её можно получить из простейших функций S 1, On, Imn конечным числом операций суперпозиции и примитивной рекурсии.

Пример n Для доказательства того, что функция является примитивно рекурсивной необходимо: 1) Согласно уравнениям (1) и (2) в явном виде определить функции g() и h(). 2) Показать, что g() и h() являются простейшими функции S 1, On, Imn либо доказанными раннее примитивно рекурсивные функции. Упр 26: Доказать, что функция f(x, y) = x+y является примитивно рекурсивной Тезис Черча: Класс алгоритмически вычислимых числовых функций совпадает с классом всех рекурсивных функций.

Машина Тьюринга n Машина Тьюринга содержит: n 1) Внешнюю память – ленту из n ячеек. Каждая i-ая ячейка находится в состоянии аi. Задан алфавит состояний. Лента может быть бесконечной в обоих направлениях. Пустые состояния опускаются. n 2) Внутреннюю память машины – устройство в текущий момент времени находится в состоянии qi. Задан алфавит внуреннего состояния. Начальное состояние q 1, заключительное q 0 или qz. n 3) Указатель – указывает на текущую ячейку и перемещается вдоль ленты. n 4) Управляющее устройство – считывает символ ячейки, на которую указывает указатель. В соответствии с программой изменяет состояние ячейки и перемещает указатель.

Состояние и программа МТ n Состояние машины Тьюринга называется слово n n n n a 1…ak-1 qi ak…ar , образованное вставкой символа внутреннего состояния перед обозреваемой ячейкой. Программа машины Тьюринга – совокупность команд, которые может выполнить машина qi aj qi’ aj’ D, где qi - внутренне состояние машины aj - состояние обозреваемой ячейки qi’ – новое состояние машины aj’ - новый символ записываемый в обозреваемую ячейку D = { L, R, E} – символы символизирующие сдвиг указателя на одну ячейку влево, вправо и отсутствие сдвига соответсвенно.

Пример МТ Упр 27: Найти конечное состояние машины Тьюринга Начальный алфавит: А = {0, 1} Алфавит внутреннего состояния: Q = {q 0, q 1, q 2} Программа: { 1) q 10 q 20 R, 2)q 20 q 01 E, 3) q 11 R, 4) q 21 R } Начальное слово: q 111

Пример МТ Упр 28 Найти конечное состояние машины Тьюринга Начальный алфавит: А = {0, 1, } Алфавит внутреннего состояния: Q = {q 0, q 1, q 2, q 3} Программа: { 1) q 1 q 00 R, 2) q 11 q 20 R, 3) q 21 R, 4) q 2 q 31 L, 5) q 30 q 00 R, 6) q 31 L } А) Начальное слово: q 111 1 Б) Начальное слово: q 11 111

Тезис Тьюринга Тезис Тьюринга: для каждого алгоритма А может быть построена машина Тьюринга, которая при одинаковых исходных данных дает те же результаты, что и алгоритм А. n Если 1 q 1 2 1 qz 2, то будем говорить, что машина Т перерабатывает слово 1 2 в слово 1 2, и обозначать это Т(1 2) = 1 2. n Запись Т() -обозначение машины Т с исходными значениями.

Нормальные алгоритмы Маркова n Нормальные алгоритмы Маркова (НАМ) преобразуют слова конечной длины друг в друга при помощи подстановки. n Задание НАМ Алфавит Подстановки u v Заключительная подстановка u v n Упр 29 Задан нормальный алгоритм Маркова: Алфавит – алфавит русского языка. Схема подстановки {Я У, Л У, С М, В Б, Р Т, Т Р, О Х, Н А} n Начальное слово СЛОН. n Найти конечное слово.

Оценка сложности алгоритмов n Предположим, что функции f(n) и g(n) измеряют эффективность двух алгоритмов, их обычно называют функциями временной сложности. Будем говорить, что порядок роста функции f(n) не больше, чем у g(n), если найдется такая положительная константы С, что | f(n) |

Эффективность алгоритмов A B C D E n 3 n 2 2 n 2+4 n n 3 2 n 1 1 мс 3 мс 6 мс 2 мс 10 10 мс 300 мс 240 мс 1 024 с 100 мс 30 с 20, 4 мс 0, 28 ч 4*1017 веков 0, 56 ч 11, 6 дней 10176 веков 1000 мс 0, 83 ч 1 мс

Теория алгоритмов n Теория алгоритмов - классифицирует задачи по сложности. При этом классифицируются лишь распознавательные задачи. n Распознавательная задача – это задача отвечающая на вопрос: обладают ли входные данные некоторым свойством. В нашем случае: входные данные – граф, свойство – является ли граф Гамильтоновым?

Классы P и NP n Сложностный класс P: существует алгоритм A, решающий задачу за полиномиальное время. n Сложностный класс NP - существует алгоритм А проверяющий предложенное решение, за полиномиальное время. n Задача о гамильтоновом цикле состоит в выяснении, имеет ли заданный граф G гамильтонов цикл относится к NP-классу.

Примеры NP задач n Задача о выполнимости булевых функций: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. n Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) данного размера. n Проблема существования гамильтонова цикла в графе. n Существование целочисленного решения системы линейных неравенств.

Возможность решения NP задач перебором n Изначально решение не известен. Поэтому важным оказывается то, что любую задачу относящуюся к NP-классу можно решить за экспоненциальное время перебором всех возможных комбинаций n Что и происходит в алгоритме по поиску цикла гамильтона

Соотношение Р и NP n Всякая задача из P принадлежит NP. n Таким образом, класс NP включает в себя класс P. В данное время, неизвестно совпадают ли классы P и NP, но большинство специалистов полагает, что нет.

Соотношение Р и NP n Если окажется, что Р= NP 1) NP задачи окажутся решаемы за разумное время. 2) Существует ряд задач, которые намеренно используют задачи экспоненциальной сложности (т. е. предполагая, что задачу решить не возможно). Например, В криптографии существует раздел о шифровании с открытым ключом, расшифровать которые практически не возможно. Если вдруг P = NP, то многие секреты перестанут быть таковыми.

NP–полные задачи n Наиболее серьезная причина полагать, что P ≠ NP - существование NP полных задач. n Неформально!!!, задача Q сводится к задаче Q′, если задачу Q можно решить за полиномиальное время для любого входа, считая известным решение задачи Q′ для какого-то другого входа. Например, задача решения линейного уравнения сводится к задаче решения квадратного уравнения.

NP–полные задачи n NP-полная задача - это такая задача из класса NP, к которой можно свести любую другую задачу из класса NP. n NP-полные задачи образуют подмножество «самых сложных» задач в классе NP. Если для любой NP-полной задачи будет найден полиномиальный алгоритм решения, то и любая другая задача из класса NP может быть решена за полиномиальное время. n Все перечисленные NP-задачи являются NP- полными. В том числе задача о цикле Гамильтона.

Можно выделить два класса языков для описания функционирования цифровых автоматов: начальные языки и стандартные или автоматные языки.

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

Для описания функционирования абстрактных ЦА на начальном языке можно использовать:

Язык регулярных выражений алгебры событий;

Язык исчисления предикатов;

Язык логических схем алгоритмов (ЛСА);

Язык граф схем алгоритмов (ГСА).

Язык ГСА совместно с языком ЛСА называют одним общим термином: язык операторных схем алгоритмов (ОСА). На практике наиболее часто используется язык ГСА.

3.3.1 Задание цифровых автоматов на стандартных
языках

Стандартные или автоматные языки задают функции переходов выходов в явном виде. К ним относятся таблицы, графы, матрицы переходов и выходов и их аналитическая интерпретация. Для того, чтобы задать автомат, необходимо описать все компоненты вектора
S = (A, Z, W, d, l, a 1).

При табличном способе задания автомат Мили описывается с помощью двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов задает функцию d (табл.3.4.), таблица выходов функцию - l (табл.3.5.). Каждому столбцу табл.3.4 и 3.5 поставлено в соответствие одно состояние из множества А , каждой строке – один входной сигнал из множества Z . На пересечении столбца a m и строки z f в табл.3.4 записывается состояние
a s , в которое должен перейти автомат из состояния a m , под действием входного сигнала z f , т.е. a s = d (a m , z f ). На пересечении столбца a m и строки z f в табл.3.5 записывается выходной сигнал w g , выдаваемый автоматом в состоянии a m при поступлении на его вход сигнала z f , т.е.
w g = l (a m , z f ).

Таблица 3.4 Таблица 3.5

Для указанных таблиц А = { a 1 , a 2 , a 3 , a 4 }; Z = { z 1 , z 2 };
W = {w 1 , w 2 , w 3 , w 4 , w 5 }.

Автомат Мили может быть задан также одной совмещенной таблицей переходов и выходов (табл.3.6), в которой каждый элемент a s /w g , записанный на пересечении столбца a m и строки z f , определяется следующим образом:

a s = d (a m , z f ); w g = l (a m , z f ).

Автомат Мура задается одной отмеченной таблицей переходов (табл.3.7), в которой каждому столбцу приписаны не только состояния a m , но еще и выходной сигнал w g , соответствующий этому состоянию, где w g = l (a m ). Для табл. 3.7 A = {a 4 , a 2 , a 3 , a 4 }; Z = {z 1 , z 2 };
W = {w 1 , w 2 , w 3 }.

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

Условие однозначности (детерминированности), которое означает, что для любой пары a m z f задано единственное состояние перехода a s и единственный выходной сигнал w g , выдаваемый на переходе.

Условие полной определенности , которое означает, что для всех возможных пар a m z f всегда указано состояние и выходной сигнал.

Таблица 3.6 Таблица 3.7

Автомат называется неполностью определенным или частичным , если либо функция d определена не на всех парах (a m z f ) Î A x Z , либо функция l определена не на всех указанных парах в случае автомата Мили и на множестве не всех внутренних состояний для автомата Мура. Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте неопределенных состояний и выходных сигналов ставится прочерк.

Граф автомата – это ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Дуга, направленная из вершины a m в вершину a s , задает переход в автомате из состояния a m в состояние a s . В начале этой дуги записывается входной сигнал z f Î Z , вызывающий данный переход: a s = d (a m , z f ). Для графа автомата Мили выходной сигнал w g Î W , формируемый на переходе, записывается в конце дуги, а для автомата Мура рядом с вершиной, отмеченной состоянием a m , в котором он формируется. Если переход в автомате из состояния a m в состояние a s производится под действием нескольких входных сигналов, то дуге графа, направленной из a m в a s , приписываются все эти входные и соответствующие выходные сигналы. Графы автоматов Мили и Мура, построенные по табл.3.6 и 3.7 приведены соответственно на рис.3.7. а, б.

Применительно к графу условия однозначности и полной определенности будут заключены в следующем:

Не существует двух ребер с одинаковыми входными пометками, выходящих из одной и той же вершины;

Для всякой вершины a m и для всякого входного сигнала z f имеется такое ребро, помеченное символом z f , которое выходит из a m .

Рис.3.7. Графы автоматов: a – Мили; б – Мура

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

Прямая таблица переходов – таблица, в которой последовательно перечисляются все переходы сначала из первого состояния, затем из второго и т.д. Табл.3.8 – прямая таблица переходов автомата Мили, построенная по графу, приведенному на рис.3.7.а.

В ряде случаев оказывается удобным пользоваться обратной таблицей переходов, в которой столбцы обозначены точно так же, но сначала записываются все переходы в первое состояние, затем во второе и т.д. Табл.3.9 – обратная таблица переходов автомата Мили, построенная по графу, приведенному на рис.3.7,а.

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

Прямая таблица переходов автомата Мура строится так же как и для автомата Мили. Разница лишь в том, что выходной сигнал w g (t ) приписывается состоянию автомата a m (t ) (табл. 3.10), либо выходной сигнал w g (t a s (t+ 1) (табл. 3.11).

Обратная таблица переходов автомата Мура строится так же как и для автомата Мили. Разница лишь в том, что выходной сигнал w g (t +1) приписывается состоянию автомата a s (t+ 1) (табл. 3.12).

В некоторых случаях для задания автомата используются матрицы переходов и выходов , которые представляют собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из a m под действием z f в a s с выдачей w g , то на пересечении строки a m и столбца a s записывается пара z f w g . Ясно, что не всякая матрица задает автомат. Как граф и таблица переходов и выходов она должна удовлетворять условиям однозначности и полноты переходов.

Системы канонических уравнений (СКУ) и системы выходных функций (СВФ) являются аналитической интерпретацией таблиц переходов и выходов или графов автоматов. СКУ – определяет функции переходов ЦА, а СВФ – определяет функции выходов ЦА.

Каждое состояние ЦА интерпретируется как событие, соответствующее множеству переходов в это состояние:

Для сокращения записи СКУ и СВФ будем в дальнейшем везде, где это возможно, опускать знаки конъюнкции и времени t в правой части уравнений типа (3.10).

Для автомата Мили, заданного табл.3.8 или табл. 3.9 запишем СКУ и СВФ (3.811и 3.12. соответственно):

Запишем СКУ и СВФ для автомата Мура, заданного табл. 3.10 - 3.12, (3.13 и 3.14 соответственно).

Элементы теории автоматов

План:

1. Понятие автомата, принцип работы автомата

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

3. Общие задачи теории автоматов

Теоретические сведения

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

Понятие автомата, принцип работы автомата

Понятие автомат рассматривается в двух аспектах:

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

2. Автомат – математическое понятие , обозначающее математическую модель реальных технических устройств. Автомат это абстрактное устройство, непонятно почему и как оно работает и, вообще, почему оно может работать. В этом аспекте автомат есть «черный ящик», который теоретически способен проводить некоторые действия. С точки зрения математики, абсолютно неважно что, как и почему производит те или иные действия.

Любой автомат должен иметь некоторое количество входов, некоторое количество выходов и некоторое количество внутренних состояний.

Алгебраическая теория автоматов является разделом теоретической кибернетики, который изучает дискретные автоматы с абстрактной алгебраической точки зрения.

Общая теория автоматов содержит различные подразделы. В зависимости от предмета изучения она делится на абстрактную теорию автоматов и структурную теорию автоматов.

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

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

Определение конечных автоматов

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

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

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

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

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

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

1. Немецкий философ и алхимик Альберт Великий с 1216 по 1246 г., создавал «железного» слугу - автомат, который выполнял в доме обязанности привратника.

2. Астроном Иоганн Мюллер (Региамонтан) (1436-1476) создал механического орла, который приветствовал наклоном головы и движением крыльев въезд в Нюрнберг императора священной Римской империи Максимилиана II.

3. Механик Жак де Вакансон (1709-1782) – автор первого в мире автоматического ткацкого станка. Он создал образ механической утки, точной копии своего живого двойника - плавала, чистила перья, глотала с ладони зерна. Его механический флейтист, исполнявший одиннадцать музыкальных пьес, поражал людей, живших в те далекие годы.

4. Русский изобретатель 19 в. А. М. Гамулецкий создал целый механический кабинет, в котором было множество сконструированных им автоматов. Здесь в том числе была и говорящая голова чародея и амур, играющий на арфе, которые поражали воображение современников.

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

6. Первый шахматный автомат был построен в 1890 г. испанским инженером Торресом Кеведо. Такой автомат мог разыграть лишь ладейный эндшпиль (король и ладья против короля).

7. Первую вычислительную машину с автоматическим управлением создал Чарльз Баббедж в 1822 г. Он спроектировал арифмометр , который имел запоминающие и арифметические устройства. Эти устройства стали прототипами аналогичных устройств современным ЭВМ.

Виды автоматов.

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

Любой автомат имеет собственные базовые множества, которые включают в себя:алфавит входа, алфавит выхода, множество состояний автомата.

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

В работе конечных цифровых автоматов важным понятием является время.

Автоматы можно классифицировать по различным признакам.

1. По виду деятельности - автоматы делятся на: информационные, управляющие и вычислительные.

К информационным автоматам относятся разнообразные справочные таблицы, информационные табло на стадионах, устройства аварийной сигнализации.

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

К вычислительным автоматам относятся микрокалькуляторы, процессоры в ЭВМ и иные устройства, выполняющие вычисления.

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

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

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

4. Абстрактные автоматы - отображающие множество слов входного алфавита Х во множество слов выходного алфавита Y.

Абстрактный автомат есть:

~ Математическая модель,

~ Алгоритм действия некоторого преобразования кодовых последовательностей,

~ Закон преобразования входного алфавита в выходной.

5. Синхронные и асинхронные автоматы . В зависимости от того, одновременно или последовательно принимаются входной сигнал и сигнал смены состояний, автоматы делятся насинхронные и асинхронные автоматы.

В синхронных автоматах продолжительность входных сигналов и время переходов согласовано между собой. Они используются в вычислительных комплексах, АСУ и т.д.

В асинхронных автоматах продолжительность входных сигналов и время переходов не согласовано между собой. Они зависят от внешних источников - различных событий, а интервал дискретности является переменным (например, в кодовых замках). В асинхронных автоматах очередное изменение значений входных сигналов может произойти только при условии, что закончился переходный процесс, вызванный предыдущим изменением этих сигналов.

6. Автоматы делятся на конечные и бесконечные автоматы. Если в основании классификации лежит объем памяти, то различие заключается в том, имеет ли автомат конечное или бесконечное число внутренних состояний.

Под бесконечным автоматом обычно понимают определенную математическую идеализацию представлений об автомате, имеющую бесконечное число состояний. Память такого автомата потенциально может неограниченно возрастать. Например, известные абстрактные автоматы Поста и Тьюринга являются бесконечными автоматами, но сама ЭВМ или ее отдельные части - конечными автоматами.

7. Автоматы делятся на детерминированные и вероятностные автоматы . Если в основании классификации лежит механизм случайного выбора, то различают детерминированные и вероятностные (стохастические) автоматы.

В детерминированных автоматах поведение и структура в каждый момент времени однозначно определены текущей входной информацией и состоянием самого автомата в предшествующий момент времени.

В вероятностных автоматах эта зависимость связана еще и с некоторым случайным выбором.

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

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

Математическая модель цифрового автомата с одним входом задается пятью объектами:

X- конечное множество входных символов, входной алфавит:

Х= {x 1 (t), x 2 (t), …, x n (t)};

Y- конечное множество выходных символов, выходной алфавит:

У={y 1 (t), y 2 (t), …, y n (t)};

Q ~ конечное множество состояний автомата:

Q= {q 0 (t), q 1 (t), q 2 (t), …, q n (t)}, q 0 - начальное состояние;

δ(q, х ) - функция перехода автомата из одного состояния в другое: (Q х X) ®Q;

λ(q, х ) ~ функция выхода автомата: (Q x Х) ® Y.

Таким образом, конечный автомат С= (X, Q, У, δ, λ.) определяется рекуррентными соотношениями

q(0) = q 0 , q(t + I) = δ (g(t), х(t)), y(t) = λ (g(t), х(t)),

t- дискретизированный момент времен или это есть образ монотонной функции t :. Т ® N, причем Т - обычное непрерывное время, N - множество натуральных чисел.

Все время работы Т разбивается на конечное число интервалов, на границе которых происходит изменение состояния автомата. При этом t(Г 0) – показывает число изменений, произошедших до момента времени Г 0 .

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

9. Синхронные автоматы делятся на автоматы Мили и автоматы Мура . В зависимости от способа организации функции выхода синхронные автоматы делятся на автоматы Мили (автоматы I рода) и автоматы Мура(автоматы II рода).

В автоматах Мили - выходной сигнал y (t) x (t) и состоянием q (t- 1) автомата в предшествующий момент времени (t- 1). Математической моделью таких автоматов служит система уравнений:

q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t-1), х(t)),

В автоматах Мура выходной сигнал y (t) однозначно определяется входным сигналом x (t) и состоянием q (t) в данный момент времени t. Математической моделью таких автоматов является система:

q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t)),

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

10. Комбинационные автоматы – есть автоматы, в которых выходной символ не зависит от его состояния и определяется лишь текущими входными символами, т.е. в этом автомате все состояния эквивалентны. В таком автомате вырождена функция перехода, она принципиально не важна и в процессе функционирования неизменна. Поэтому минимальный комбинационный автомат имеет лишь одно состояние.

11 Логические автоматы – есть автоматы у которых входной алфавит состоит из 2 т двоичных наборов длины т, а выходной - из 2 n двоичных наборов длины п. Для логических комбинационных автоматов функция выхода имеет вид системы п логических функций от т переменных.

Баранов Виктор Павлович. Дискретная математика. Раздел 6. Конечные автоматы и формальные языки.

Лекция 31. Определение и способы задания конечного автомата. Задача синтеза. Элементарные автоматы

Лекция 30. ОПРЕДЕЛЕНИЕ И СПОСОБЫ ЗАДАНИЯ КОНЕЧНОГО АВТОМАТА.

ЗАДАЧА СИНТЕЗА. ЭЛЕМЕНТАРНЫЕ АВТОМАТЫ

План лекции:

1. Определение конечного автомата.

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

1. Задача синтеза автоматов.
2. Элементарные автоматы.
3. Задача о полноте автоматного базиса.
4. Канонический метод синтеза автомата.

1. Определение конечного автомата

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

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

Во-вторых, предполагается, что время изменяется дискретно. Состояния входа и выхода соответствуют дискретной временной последовательности Поскольку момент времени однозначно определяется его индексом, то с целью упрощения будем считать, что время принимает значения 1, 2, …, … Временной промежуток называется тактом.

Работа автомата представляется следующим образом.

На вход автомата поступают сигналы из входного алфавита, что приводит к появлению сигналов на выходе из входного алфавита. Зависимость выходной последовательности от входной зависит от внутреннего устройства автомата. Заметим, что в отличие от СФЭ, которые не обладают памятью, автомат представляет собой устройство с памятью, т. е. выход автомата определяется не только входом, но и предысторией. Учет предыстории осуществляется зависимостью выходного сигнала не только от входа, но и от текущего состояния, которое обозначим.

Дадим формальное определение автомата.

Конечным автоматом называют пятерку объектов

– конечное множество, называемое входным алфавитом; – одно из возможных состояний входа;

– конечное множество, называемое выходным алфавитом; элементы этого множества определяют возможные состояния выхода;

– конечное множество, называемое алфавитом внутренних состояний;

– функция переходов автомата: ; эта функция каждой паре «вход-состояние» ставит в соответствие состояние;

– функция выходов автомата: ; эта функция каждой паре «вход-состояние» ставит в соответствие значение выхода.

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

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

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

Пример 1. Зададим автомат следующим образом: , .Функцию определим с помощью таблицы переходов, а функцию – с помощью таблицы выходов.

Таблица 1. Таблица переходов Таблица 2. Таблица выходов

Если известна последовательность сигналов на входе автомата, то таблицами переходов и выходов однозначно определяется выходная последовательность.

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

Рис.1 Диаграмма переходов-выходов

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

Автомат находится в состоянии 1, если при сложении предыдущих разрядов возникает перенос, и в состоянии 0 – в противном случае. Диаграмма переходов-выходов показана на рис. 2.

1. Задача синтеза автоматов

По аналогии с задачей синтеза СФЭ можно поставить задачу синтеза для автоматов. Имеется неограниченный набор базисных автоматов. Требуется собрать автомат с наперед заданным функционированием. При этом задача синтеза сталкивается с определенными проблемами.

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

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

Пусть – конечное множество из элементов, а – множество двоичных слов длины, где. Произвольное инъективное отображение будем называть кодированием множества двоичными словами.

Произведем кодирование алфавитов для произвольного автомата:

Обозначим закодированные вход, выход и состояние автомата в момент времени соответственно. Тогда закон функционирования представится в виде

Полученный после кодирования автомат называют структурным. Будем считать, что структурный автомат имеет двоичных входов, двоичных выходов, а внутреннее состояние автомата задается двоичным словом длины. На рис. 3 показан абстрактный автомат и соответствующий ему структурный автомат.

Переход к структурному автомату обеспечивает два важных для синтеза преимущества.

1. Совместимость входов и выходов, так как через них передается двоичная информация. Мы не будем давать общее определение схемы из структурных автоматов – оно аналогично СФЭ.

2. Запишем соотношения (2) в «координатах»:

Из (3) следует, что закон функционирования структурного автомата задается системой булевых функций.

1. Элементарные автоматы

Выделим простейшие структурные автоматы и дадим им название.

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

Перейдем к автоматам с двумя состояниями. Пусть автомат имеет один двоичный вход и один двоичный выход, совпадающий с внутренним состоянием: :

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

Таблица 3

Вместо звездочек нужно поставить 0 и 1. Это можно сделать 16 способами, однако, не все они приемлемы. Допустим, например, что в первом столбце таблицы 3 оба элементы нули. Такой автомат, оказавшись в состоянии 0, более из него не выйдет, то есть будет работать как функциональный элемент. Анализ аналогичный ситуаций показывает, что для того чтобы получился автомат, не сводящийся к автомату без памяти, надо потребовать, чтобы в каждом столбце таблицы 3 встречались и ноль и единица. Таких таблиц всего четыре.

Таблица 4 Таблица 5

Таблица 6 Таблица 7

Имеем только два простейших автомата, так как 7 получается из 4, а 6 из 5 путем инверсии внутренних состояний.

Автомат, задаваемый таблицей 4, называется задержкой или -триггером:

то есть этот автомат задерживает сигнал на один такт.

Автомат, задаваемый таблицей 5, называется триггером со счетным входом или -триггером. Состояние автомата меняется на противоположное, если на вход поступает 1, и остается без изменения, если на вход поступает 0:

Пусть в начальный момент времени -триггер находится в состоянии 0. Если в некоторый момент времени -триггер находится в состоянии 0, то это означает, что на вход автомата поступило четное число единиц. Если в состоянии 1, то – нечетное. Таким образом, -триггер считает количество единиц на входе, но так как он имеет всего два состояния, то и считает до двух.

При физической реализации триггеров используют два выхода: прямой и инверсный (рис. 5). Если поменять их местами, то из -триггера получится автомат, задаваемый таблицей 7, а из -триггера – автомат, задаваемый таблицей 6.

1. Задача о полноте автоматного базиса

Набор структурных автоматов называется полным (или автоматным базисом), если из них можно построить любой наперед заданный структурный автомат.

Усилия математиков для получения аналога теоремы Поста для автоматов не увенчались успехом. В 1964 г. М.И. Кратко доказал несуществование алгоритма для определения полноты системы. В этом случае представляют интерес варианты теоремы о полноте с дополнительными предположениями о системе. Рассмотрим наиболее популярный из них.

Теорема. Система автоматов, содержащая полный набор ФЭ и -триггер (или -триггер) является полной.

Доказательство. Рассмотрим произвольный автомат, заданный соотношениями (2), и опишем его схему из указанных автоматов, называемую канонической структурой (рис. 6).

Схема состоит из двух частей.

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

то это означает, что автомат находится в состоянии.

Правая половина называется комбинационной частью и представляет СФЭ. Входы этой схемы:

1. двоичное слово – входной сигнал автомата;
2. двоичное слово – текущее внутреннее состояние автомата.

1. двоичное слово – выходной сигнал автомата, который реализуется по формулам (3);
2. двоичное слово, которое поступает на входы триггеров в запоминающей части и управляет памятью автомата.

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

В каждый момент времени сигналы управления памятью должны переводить автомат из состояния в состояние. Для этого надо изменить состояние каждого триггера

Используемые в канонической схеме -триггеры или -триггеры обладают следующим свойством: для любой пары состояний существует входной сигнал, переводящий автомат из состояния в состояние. Обозначим этот сигнал через. Для -триггера, так как состояние, в которое устанавливается -триггер, равно входному сигналу. Для -триггера: при на вход надо подать 0, чтобы состояние не изменилось; при – 1, чтобы триггер «перевернулся».

Итак, или в векторной форме

Выразим из закона функционирования автомата (2). Тогда

Теорема доказана.

1. Канонический метод синтеза автомата

Рассмотрим этот метод на конкретном примере.

Пример. На конвейере, по которому двигаются детали двух типов и, установлен автомат, задачей которого является такая сортировка деталей, чтобы после прохождения мимо автомата они образовывали группы. Неподходящую деталь автомат сталкивает с конвейера. Требуется построить схему такого автомата, используя -триггер и элементы «И», «ИЛИ», «НЕ».

Синтез автомата разбивается на следующие этапы.

1. Построение абстрактного автомата.

Входной алфавит – . Выходной алфавит – , где С – сталкивание детали, П – ее пропуск. Внутренние состояния автомата отражают его память о том, какую часть группы он уже сформировал: . По мере формирования группы автомат циклически перемещается по этим состояниям, не изменяя состояния при поступлении неподходящей детали. Диаграмма переходов-выходов показана на рис. 7.

2. Кодирование алфавитов.

Один из возможных вариантов кодирования приведен в следующих таблицах.

Вход Выход Состояние

3. Построение канонической структуры автомата.

Каноническая структура разрабатываемого автомата показана на рис. 8.

Найдем зависимости выходов СФЭ, от переменных сначала в табличном виде (таблица 8), по которым далее построим формулы

Таблица 8

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

4. Представление функций выхода автомата и функций управления памятью формулами.

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

5. Реализация СФЭ и окончательная схема автомата (рис. 9).

ОПРЕДЕЛЕНИЕ И СПОСОБЫ ЗАДАНИЯ КОНЕЧНОГО АВТОМАТА. ЗАДАЧА СИНТЕЗА. ЭЛЕМЕНТАРНЫЕ АВТОМАТЫ

Главная » Полезно знать » Конечные автоматы способы задания и основные свойства. Определение и способы задания конечного автомата