Материал: дискретка

Способы задания

1 способ. усеченное дерево . Для любой усеченной детермин. функции соответствующее ей бесконечное информативное дерево можно свести к конечному. Для этого надо :

1. Перенумеруем классы эквивалентности таким образом что бы класс в которое попадет исходное дерево имело № 0

2. Берем произвольную вершину и присваиваем ей № q класса в которое попадает дерево с корнем в вершине

3. Берем произвольную ветвь

Т.к ф-ия огр.-дет. то найдется такое число j что ( то есть номера начнут повторяться) и для всех пар так что номер о является наименьшим

4. Проведем усечение ветви сохранив ее нач-ый отрезок до вершины

2 Способ

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

Расписать состояние значит указать состояние в котором можно попасть из него

Диаграмма мура

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

1. Наносим произ-ым образом на плоскость сост. в виде точек, нумеруем их №, соотв. № состояний. Корневая вершина получается «*».

2. Идем от корня по усеченному дереву и каждую дугу дерева отображаем на диаграмме. При этом важно указывать направление.

Диаграмма Мура.

3. способ Канонические уравнения

Пусть F - огр.дет ф-ия. Рассмотрим диаграмму мура.

Предположим что в момент времени (t-1) мы нах. в вершине q(t-1) тогда при поступлении в момент времени t числа (t) мы переместимся в диаграмме по ребру (t) выходящему из вершины q (t) при этом получим выходное значение (t) и перейдем в вершину q (t)

Т.о величины однозначно опр. величины

Введенные величины и будем называть соотв. входной и выходной величинами, а q состоянием.

Пусть переменные X Y Q таковы что : Х описывает значение входной величины ,Q описывает состояние q и Y опис. значение выходной величины .

Получаем что с помощью Д.М можно создать две функции.

F: A Q B функция выходов

G: A Q Q функция переходов

На основании приведенных выше рассуждений мы приходим к след. уравнениям.

(1)

Где

Это канон. урав. с в векторной форме с начальным условием q,

5. способ Канонические таблицы

6. способ Аналитические задания.

7. способ. Бесконечное информ. дерево.

Вместо канон. урав.(1) бывает удобно рассматривать канон. урав. в которых функция выходов и переходов явл. формулами K-значной логики. Для получения соотв. представления ф-ии F алфавиты A, B, Q кодируется векторами (наборами) координаты (компоненты которых пренад. множеству

Если F – ограничено-детерм. ф-ия и , , то для кодирования букв из алфавита A, B, Q достаточно взять векторы имеющие длины n, m, r соответственно.

Система (1) преобразуется тогда в следующую

(2)

Используются такие векторная запись систем аналогичных системе (2) При такой записи система (2) примет вид

(3)

Ф-ии и в системе (2) явл-ся частичными, т.е не всюду определенными.

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

Операции над детерминированными функциями.

Пусть детерминированная ф-ия F задана системой (2) и каждая из функций и всюду определенные функции к-значной логики.

Будем рассматривать ф-ию f как элемент мн-ва

Обозначим схему реализующую ф-ию f.

Схему будем изображать в виде прямоугольника с n входами и m выходами. Входы изображаются в виде стрелок исходящих из входных полюсов. Выходы - стрелки из выходных. Полюса- кружочки.

Если m=1 то схему реализующую ф-ию.f иногда изображают в виде треугольника с n входными и одним выходным полюсами.

Считаем что в каждый момент времени t=1, 2 на i-ый вход поступает входной символ а на j-ом выходе выдается значение.

Операции

1) Операция отождествление 2-х или > или числа входных переменных в ф-ии f

В результате этой операции происходит отождествление в схеме соотв-х этим переменным входных полюсов.

2) Операция удаление некоторой выходной переменной . Данная операция эквивалентна выбрасыванию из системы (2) уравнения И удаление из схемы выходного канала и полюса .

3) Операция введение обратной связи по одной входной и 1ой выходной переменным.

4) Операция операция объединения 2х или > функций.

5) Операция S-суперпозиция

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

Опр. М.Т-это абстрактное устройство сост. ее из бесконечной ленты считывающей головки и управ-го устройства или конечного автомата.

ОПР.

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

Теорема Черча

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