double arrow

Рекурсивные функции. Детерминированным конечным автоматом называется произвольная пятерка следующего вида: M ={Q, , δ

2

Конечные автоматы

Детерминированным конечным автоматом называется произвольная пятерка следующего вида: M ={Q, , δ, S ,F}

При этом:

Q, , F – конечные множества

S Q, F Q, δ:Q →Q

δ – функция перехода из Q →Q

– алфавит автомата М (входной)

Q – множество состояний конечного автомата (внутренний алфавит)

S – начальное состояние

F – множество конечных состояний

δiq1q2 Q и a q2 = δ(q1,a)

Если q1q2 Q и для некоторых a можно записать q2 = δ(q1,a), то говорят что автомат М переходит из состояния q1 в состояние q2 под действием а.

Конечные автоматы изображаются графами(рис.3): вершины – состояния, дуги – переход из 1 состояния в другое при этом над дугой пишут символы, под влиянием которых осуществляется переход.

Рисунок 3 – Изображение конечного автомата.

∆ - начальное состояние

- конечное состояние

= {a,b}

Q = {q0, q1}

S = q0

F = {q1}

  Q   a   b
q0 q0 q1
q1 q0 q1

Пример:является ли слово mamba подсловом некоторого алфавита.

= {m,a,b,_,др}

Q = {q0, q1, q2, q3, q4, q5, q6}

S = q0

F = {q5, q6}

  Q   a   b   m   _   др
q0 q0 q0 q1 q6 q0
q1 q2 q0 q1 q6 q0
q2 q0 q0 q3 q6 q0
q3 q2 q4 q1 q6 q0
q4 q5 q0 q1 q6 q0

Кодирование входного алфавита и состояний




  С
a
B
m
_
др
Q С
q0
q1
q2
q3
q4
q5
q6

Реализация конечного автомата

Q^t Q^(t+1)
X0 X1 X2 R0 R1 R2 R0 R1 R2
                   

Составим функцию для r0:

r0 = x0x1x2 r0x1x2 r0r1r2x1x2

Составим функцию для r1:

r1 = r0x1x2 r0r1r2x1 r1r2x1x2 r1r2x1x2

Составим функцию для r2:

r2 = r1r2x1x2 r1x1x2 x0x1x2 r1r2x1x2

Самая первая алгоритмическая система.

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

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

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



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

Гипотеза Черча:класс рекурсивных функций тождественен с классом всюду определенных вычислимых функций.

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

Простые функции:

Ø тождественно равные нулю

0n(x1, x2, …, xn) = 0

n – количество аргументов

Ø повторяющая значение аргумента

Iin (x1, x2, …, xn) = xi

Ø функция непосредственного следования

S1(x) = x+1

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

В теории алгоритмов наиболее важными являются 3 метода построения сложных функций:

Ø суперпозиция

Ø примитивная рекурсия

Ø наименьшего корня



2




Сейчас читают про: