Материал: Методичка Дзержинский

RS -_триггер

Таблица 4

Так как разные состояния полного автомата Мура дают различные выходы,

то можно считать, что между алфавитом состояний Q и выходным алфавитом B имеются взаимооднозначные соответствия. Поэтому можно считать, что алфавит Q и B совпадают . Отождествив соответствующие буквы алфавитов. Тогда F(q)=q, то есть функция выходов будет тождественной и в определении полного автомата Мура может не указываться.

11

Рассмотрим некоторую совокупность автоматов ∑.

Определение: Система ∑ называется автоматно-полной, если любой конечный автомат может быть реализован в виде ССА, в которой участвуют только автоматы из системы ∑ (ССА над cистемой ∑).

Теорема (достаточное условие автоматной полноты).

Для того чтобы система автоматов была полной, достаточно чтобы она содержала хотя бы один полный автомат Мура и некоторую функциональнополную систему функциональных элементов. { M, f1…fS }

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

Представим линии задержки в виде схемы автоматов следующего вида: есть входящий сигнал х(t), есть полный автомат Мура М, логические блоки F и Ф, то есть комбинационные схемы, содержащие функциональные элементы f1…fS F – блок выхода. Ф – блок возбуждения памяти. Они формируются следующим образом. Так как М – полный автомат Мура, то берем фиксированные два состояния q0 и q1 QM и будут существовать буквы а0 и а1, так что для q при подаче на вход М буквы а0 переведет автомат М в состояние q0, а при подаче на вход а1 переведет автомат М в состояние q1. Пусть блок Ф выдает букву а0, если на вход получил х=0, а автомат М находился в состоянии q, и выдает букву а1, если на вход подается х=1, а автомат М находится в состоянии q, то есть если на вход блока Ф послать сигнал 0, то блок Ф выработает сигнал, переводящий автомат М в состояние q0, а если на вход блока Ф послать сигнал 1, то блок Ф выработает сигнал, переводящий автомат М в состояние q1.

Блок F на состояние q0 создает символ 0, а на состояние q1 символ 1, а на остальных состояниях выход доопределяем произвольным образом. Такой автомат работает как задержка.

Если на вход х=0, то выход Ф равен a0(q), то есть q → q0, а на выходе F будет 0, но через один такт (так как стоит полный автомат Мура).

Если на вход х=1, то выход Ф равен? a1(q), то есть q → q1, а на выходе F будет 1, но через один такт.

Пример.

Структурный синтез автоматов

12

Пусть задана некоторая автоматно полная система Σ. Требуется представить автомат схемой (ССА) над Σ. Это называется структурный синтез.

Каноническая программа синтеза (алгоритм Хоффмана-Глушкова)

1)По описанию автоматического отображения составляется автоматная таблица.

2)Минимизируется число состояний полученного автомата.

3)Производится двоичное кодирование алфавита.

4)Строится автоматная таблица для полученного логического

автомата.

5)Строится таблица управления памятью по полному автомату

Мура.

6)Записываются канонические уравнения и уравнения для управляющих памятью функций.

7)Функции реализуются в виде схем.

Примеры:

Машина Тьюринга

Опр.: Машина Тьюринга Т – это пятерка объектов Т={A,Q,F,G,H}

A – входной и выходной алфавит, Q – алфавит состояний, F – функция выхода, G – функция перехода, H – функция управления

Работа машины Тьюринга описывается следующим образом.

Имеется бесконечная лента, разделенная на ячейки. В ячейках выписывается либо пустой символ …, либо другая буква алфавита A.

На каждом шаге машина прочитывает входную букву, переходит в новое состояние согласно ф.G, печатает вместо прочитанной буквы новую согласно ф.F и сдвигается вправо, влево или остается на месте в зависимости от ф.H.

Способы задания машины Тьюринга.

1)Автоматная таблица

На пересечении i-той строки (аi) и j-того столбца (qj) записывается новая буква а’, новое состояние q’ и управляющий символ h

2)Программа

Запись aiqj – a’q’h называется командой машины Тьюринга. Она

13

описывает работу Т в один из множеств моментов времени. Список какого-либо множества команд будем называть программой или списком. Программа задает работу машины Тьюринга.

Замечания:

Команды не обязательно содержат в левых частях все возможные сочетания (a, q), а только те, которые реально встречаются в процессе работы.

Утверждение 1

Головка машины Тьюринга есть конечный автомат. Из описания машины Т следует, что головку машины можно рассматривать как конечный автомат М, у которого А=А, Q=Q, B=Ax{R,L,S}, функции F’(a,q), G’(a,q) определяются из программы работы машины Тьюринга:

Утверждение 2

Функционирование любого конечного автомата можно смоделировать на машине Тьюринга. Пусть конечный автомат М={A,Q,B,G,F}.

Утверждение 3

Возможности машины Тьюринга больше чем у конечного автомата.

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

Вычисления на машинах Тьюринга

Определение

Конфигурацией машины Т называется всякая запись в явном виде, указывающая состояние считывающей головки и то, что записано на ленте αqi β; α – то слово, что находится слева от головки на листе, β –то, что находится справа.

Определение

Конфигурация Т, в которой головка смотрит на первую (левую) ячейку массива информации, записанной на ленте, называется правильной конфигурацией.

14

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

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

На ленте натуральное число х будет записываться массивом из х единиц … Числа на ленте будем разделять символом «*», если пустой символ … , то это ноль.

Рассмотрим произвольную функцию y=f(x1…xn), где xi – целые неотрицательные числа, y – принимает целое неотрицательное значение.

Функция f(x1…xn) называется вычислимой по Тьюрингу, если существует машина Тьюринга, работающая следующим образом: для любой совокупности чисел x1,x2…xn, для которых функция f определена, машина Тьюринга, начав работу из начальной конфигурации q01x*1x2…1xn, заканчивает работу конфигурацией q01y, где y=f(x1…xn). Если f на совокупности x1..xn не определена, то машина Тьюринга работает бесконечно.

Вычислимость суперпозиции:

Пусть заданы две функции: y=f(x) и z=g(y), причем z определена на области значений функции f, тогда функция z=g(f(x)) называется суперпозицией функций f и g или композицией.

Теорема. Если функции f и g вычислимы по Тьюрингу, то их суперпозиция тоже вычислима по Тьюрингу. И машину Т=Тg Тf называют композицией исходных машин Тьюринга.

Доказательство. Чтобы написать программу для композиции, надо объединить обе программы и сделать следующие изменения: во всех командах первой программы для функции f, где встречается заключительное состояние q(z1), его надо заменить на начальное состояние второй программы q02.

Вычислимость (разветвления) условного перехода.

Определение. Пусть x1,x2…xn символы переменных произвольной природы. n-местным предикатом P(x1…xn) называется высказывание об

15