Элементами. Из определения следует, что элементы множества обладают двумя свойствами 1 вполне различимы 2

• Название: Элементами. Из определения следует, что элементы множества обладают двумя свойствами 1 вполне различимы 2
• Дата: 16.01.2018
• Размер: 0.67 Mb.
• Имя файла: shpora_dmiml.docx
• Тип: Документы; #34346
• страница: 8 из 9

Диаграммой состояний наз. ориентированный граф в котором количество вершин равно количеству состояний данного автомата и помечена символами внутренние cсостояние.

Дуга выходящая из любой вершины q_i помечается символами α_t , β_r .

При этом: δ(α_t , β_r) = q_i λ(α_{t ,} q_i) = β_r

Автомат наз. инициальным, если он всегда начинает свою работу из одного и того же состояния и неинициальным если начинает свою работу с любого состояния.

Автомат δ в общем случае является частичным и недетерминированным.

Если D≤A×Q отображение Г , то автомат S всюду определенным и недетерминированным. Если задает функция отображения Г то всюду определенный и детерминированным.

Поскольку автомат (1) задет функция (2) , то он относится к вектору определения детерминированного конечного автоматом.

Если А=В={0,1} то автомат S наз. логическим автоматом.

Автомат вида (1) наз. конечным автоматом Мили ( I рода) при этом поведение автомата (1) определяется парой функций

q_i(t)= δ(q_i(t-1), q_j(t))

b_i(t)= λ(q_i(t-1), q_j(t)) q_i(t-1), q_j(t) - предыдущее и последнее состояние автомата.
Автомат Мили – синхронный конечный автомат.

Автомат II рода описывается функциями q(t)= δ(q(t-1), а(t)) b(t)= λ(q(t-1), а(t))
! Для каждого автомата II рода сущ. эквивалентный ему автомат I рода.

! Между автоматами I и II рода сущ. взаимооднозначное соответствие.

Примером автомата II рода может быть автомат Мура: q(t)= δ(q(t-1), а(t)) b(t)= λ( а(t))

Автомат Мура – автономный автомат без входа.
68.Дешифратор.

Дешифратором наз. инициальный конечный автомат входным алфавитом которого явл. алфавит А={0,1}.

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

При этом α – код комбинированных данных автомата.

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

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

Автоматы А₁ и А₂ эквивалентны, если для любого q_i автомат А₁ найдется эквивалентны ему q_j автомат А₂ , а так же для каждого q_j* автомат А₂ найдется эквивалентное ему сост. q_i* автомата А_1.

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

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

69.Реализация автоматов схемами.

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

Функциональный элемент изображается так:

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

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

Элемент задержки изображается так:

Верхний отросток называется входом, а нижний — выходом элемента задержки.

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

индуктивно:

а) совокупность полюсов (кружков, помеченных символами переменных) есть схема; все полюсы являются её вершинами',

б) результат присоединения к вершинам схемы всех входов некоторого элемента (функционального элемента или элемента задержки) есть схема; вершинами новой схемы являются все вершины исходной схемы и выход присоединённого элемента,

а полюсами — все полюсы исходной схемы;



в) результат присоединения выхода задержки к некоторому полюсу x_i есть схема; её вершинами являются все вершины исходной схемы, за исключением х-, а полюсами — все полюсы исходной схемы, кроме x_i. Операция, соответствующая пункту в), называется введением обратной связи.
70. Ограниченно детерминированные функции. Информационные деревья.

Если А- какой-либо алфавит, то пусть A* обозначает множество всех слов, а A⁰ - множество всех слов или множество всех сверхслов в алфавите А. Функция f, отображающая A⁰ в B⁰ , где Аи В- произвольные конечные алфавиты, наз. детерминированной функцией, если выполняются следующие два условия:

1) для любого α из A⁰ длина f(α) равна длине а

2)если-α слово длины l где  α₁ = αα’ , α₂ = αα’’, α’, α’’Є A⁰ , то значения f(α₁) и f(α₂) имеют одинаковые начала длины l.

Если детерминированная функция f определена на множестве  всех сверхслов в алфавите А, то в силу условий 1) и 2) она однозначно распространяется на множество A*: для произвольного слова α длины l значение f(a) совпадает с началом длины l значения f(αβ) , где β- произвольное сверхслово в алфавите А. Таким образом, всякая детерминированная функция f удовлетворяет условию:

3) для любого слова α из A* и любого β из A⁰ справедливо равенство f(αβ) = f(α)f_α(β),  где f α - некоторая детерминированная функция на множестве A⁰ , однозначно определяемая словом α.

Функция f_a ,наз. остаточной функцией для f. Из условия 3) следует, что всякая детерминированная функция f определяет на множестве A* отношение эквивалентности R: αRβ  тогда и только тогда, когда fα=fβ . Ранг этого отношения, или, что то же, максимальное число попарно различных остаточных функций, наз. весом детерминированной функции f.

Если вес детерминированной функции конечен, то она наз. ограниченно-детерминированной функцией. Это понятие распространяется и на функции от т-переменных, где m≥2  если наборы из т-слов одинаковой длины (или сверхслов) в алфавитах A₁, … , A_m соответственно рассматривать как слова (сверхслова) в алфавите A₁× … × A_m  , являющемся декартовым произведением алфавитов A₁, … , A_m . Таким же образом можно рассматривать О.-детерминированной функции с несколькими выходами, т. е. значениями которых являются наборы из к-слов или сверхслов соответственно в алфавитах B₁, … , B_k Класс всех О.-детерминированной функции совпадает с классом функций, вычислимых конечными автоматами. Поэтому для задания О.-детерминированной функции могут быть использованы те же средства, что и для задания конечных автоматов, например, каноническое уравнения (см. Автомат конечный, Автоматов способы задания). Отсюда следует, в частности, что класс О.-детерминированной фунции с совпадающими алфавитами A₁= … =A_m = B замкнут относительно суперпозиций. Минимальный (по числу состояний) автомат U(A, S, B, φ, ψ, s₁ ) вычисляющий О.-детерминированной функции f веса т, содержит п-состояний и может быть построен следующим образом. Пусть α₁, …,α_n - произвольные представители всех классов эквивалентности отношения R. Каждому классу R(α_i), i=1, … , n , ставится в соответствие некоторое состояние s_i автомата U. Функция переходов j и функция выходов ψ определяются следующими условиями: если aЄA и 1≤ i ≤n, то φ(s_i, a)=s_{j ,} где состояние s_j соответствует классу R(α_i a); ψ(s_i, a)=fα_i(a).  В качестве начального берется состояние, соответствующее классу R(е), где е - пустое слово.
71. Понятие алгоритма. Основные свойства алгоритмов. Вычислимость.

Под алгоритмом понимается способ преобразования представления информации.

Основные особенности алгоритма:

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

Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, её вычисляющий, то есть такой алгоритм A, что

• если f(n) определено для некоторого натурального n, то алгоритм A останавливается на входе n и печатает f(n);

• если f(n) не определено, то алгоритм A не останавливается на входе n.

Несколько замечаний по поводу этого определения:

1. Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое под множество натурального ряда). Например, нигде не определённая функция вычислима (в качестве A надо взять программу, которая всегда зацикливается).

2. Можно было бы изменить определение, сказав так: «если f(n) не определено, то либо алгоритм A не останавливается, либо останавливается, но ничего не печатает». На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).

3. Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0, 1}), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, «конструктивные объекты». Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.
72. Рекурсивные функции. Операторы суперпозиции и примитивной рекурсии.

Исходными функциями являются:

1) z(х) = 0 — нуль функция;

2) N(x) = х + 1 — функция следования:

3) I_k(x₁,...,x_n) = X_k k=1…n. —селекторная функция, (функция выбора аргумента, проектирующая функция)

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

Целочисленные компоненты вводятся как суперпозиции функций z(x) и N(x): N(z(x))=0+1=1 N(N(z(x)))=2

Функцию g(x)=x+z можно записать как:

N(N(I₁(x))) = (x+1)+1=x+2

Говорят, что функция n получается применением операции суперпозиции S, функция f,g₁,…,g_n при этом записывается так:

h= S( f,g₁,…,g_n) если h(x₁,...,x_n)= f(g₁( x₁,...,x_n),…, g_n( x₁,...,x_n))

Говорят, что функция f зависящие от h+1 переменной получаются применением оператора примитивной рекурсии R к функция g(x_n) и h(x_n+1) если f=R(g,h):

1)f(x₁,...,x_n,0) = g(x₁,...,x_n)

2) f(x₁,...,x_n,k+1)=h(x₁,...,x_n,k,f(x₁,...,x_n,k)) k=N {0}

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

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


73. Примитивно рекурсивные предикаты. Свойства.

Предикат Р(х₁,…,х_n) называется примитивно рекурсивным если его характеристическая функция является примитивно рекурсивной.

Характеристическая функция X_p (х₁,…,х_n )=0 или 1, 0 если Р(х₁,…,х_n)-ложно; 1 если Р(х₁,…,х_n) – истина

Функция X рассматривается как функция натуральных элементов.

Свойства:

Опр.1 Если P,Q – примитивно рекурсивные предикаты, то ^---P, P&Q, PQ, PQ, P*Q , PQ также примитивно рекурсивные предикаты

Опр.2 Пусть P₁(х₁,…,х_n) , … , P_k(х₁,…,х_n) примитивно рекурсивные предикаты, причем P_i&Q _j =0, для всех ij, а P₁ P₂…. P_k 1 т.е при любом наборе переменной (х₁,…,х_n) только один из предикатов P_i i=1,k равен 1 и пусть функция g₁(х₁,…,х_n)…. g_k(х₁,…,х_n) примитивно рекурсивные предикаты P_i&Q _j =0 функция f(х₁,…,х_n) = g₁(х₁,…,х_n), P₁ 1

g_k(х₁,…,х_n), P_k 1,тогда функция также является примитивно рекурсивной

опр.3Если функция f(х₁,…,х_n,y) примитивно рекурсивная функция, то ограниченная сумма:

g(x₁,...,x_n,a) = (х₁,…,х_n,y) и если f(х₁,…,х_n,0)=0 также является примитивно рекурсивной функция.

опр.4 Если функция f(х₁,…,х_n,y) примитивно рекурсивная функция, то ограниченное произведение g(x₁,...,x_n,a) = (х₁,…,х_n,y) при условии, что f(х₁,…,х_n,0)=1 также является примитивно рекурсивной функцией.

опр.5 Если P(х₁,…,х_n,y) примитивно рекурсивный предикат, то огранич кванторы Q₁(х₁,…,х_n,a) = y P(х₁,…,х_n,y) в случае если P(х₁,…,х_n,0)=1 а также Q₂(х₁,…,х_n,a) = y P(х₁,…,х_n,y).

Если P(х₁,…,х_n,0)=0 также, является примитивно рекурсивными предикатами.
74. Классы рекурсивных функций. (п.р., о.р., ч.р.). Тезис Черча.

Функция f(х₁,…,х_n,z) называется результатом примитивно ограниченный оператор минимизации (-оператор) к предикату P(х₁,…,х_n,y), если функция f равна такому значению у = {0,1…z} при котором значение предиката Р(х₁,…,х_n,y) = 1 а для ty значение предиката Р(х₁,…,х_n,y)=0

В этом случае записывают: f(х₁,…,х_n,z)=yP(х₁,…,х_n,y)

Теорема: Если Р(х₁,…,х_n,y) примитивно рекурсивный предикат, то функция yP(х₁,…,х_n,y) является примитивно рекурсивной