Конечные автоматы. Рассмотрим движение системы из N мат

Основные понятия теории алгоритмов

Алгоритмами называются конструктивно задаваемые соответствия между словами в абстрактных алфавитах.

Абстрактный алфавит – любая конечная совокупность объектов, называемая буквами или символами данного алфавита. Любой алфавит задается перечнем его символов: A={a, b,c}.

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

Длиной слова называется количество символов слова.

Пустое слово – слово нулевой длины.

Слово Р – под-слово слова Q если слово Q представляется в виде: q=pr. Алфавитным оператором (отображением) называется всякое соответствие сопоставляющие словам алфавита А слова того же или другого алфавита. При этом первый алфавит называется входным, а второй выходным данного оператора.

Алфавитный оператор – функция, задающая отношение Га = в.

Алфавитный оператор задается:

· графично(рис.1)

· таблично

A	B
a	kl
b	km
c	mm
d	kl
d	km

Рисунок 1 – Задание алфавитного оператора графично.

Различают однозначные и многозначные алфавитные операторы.

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

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

Рисунок 2 – однозначный алфавитный оператор.

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

Совокупность всех слов, на которых определен алфавитный оператор называется областью его определения.

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

Процесс обратный кодированию – декодирование.

Декодирующий оператор Г^-1В=а.

Пример:

A	B
a	k
b	kl
c	ml
d	ll

aabacd → kkklkmlll

Для обратимости кодирования должны выполняться два условия:

1. коды разных символов входного алфавита должны быть различны;

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

Кодирование, при котором все коды имеют одинаковую длину, называется нормальным.

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

Для определения длины кодового слова используется формула:

Тогда l ≥ log_mn

m – количество символов в выходном алфавите;

l – длина кодового слова,

n – количество символов входного алфавита.

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

Свойства алгоритмов:

1. Равнозначность.

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

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

2. Эквивалентность.

Два оператора эквивалентны, если у них совпадают алфавитные операторы, но не совпадает система правил.

Алгоритмы, основанные на однозначном алфавитном операторе, называются детерминированными.

3. Массовость.

Алгоритм называется массовым, если он применим для множества входных слов.

4. Результативность.

Если алгоритм обеспечивает получение результата через конечное число шагов, то он называется результативным.

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

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

Алгоритмы бывают:

Ø случайные;

Ø самоизменяющиеся.

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

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

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

Алгоритмические системы делятся на:

Ø алгебраические;

Ø геометрические.

Алгебраическая система строится в некоторой конкретной символике, в которой алгоритмы представляются в виде линейных текстов:

Ø рекурсивные функции;

Ø машина Тьюринга;

Ø операторные системы Ван-Хао;

Ø логические схемы Янова.

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

Ø конечные автоматы;

Ø нормальный алгоритм Маркова;

Ø блок-схемы.

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

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

При этом:

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

S Q, F Q, δ:Q →Q

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

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

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

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

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

δ_iq₁q₂ Q и a q₂ = δ(q₁,a)

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

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

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

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

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

= {a,b}

Q = {q₀, q₁}

S = q₀

F = {q₁}

Q	a	b
q0	q0	q1
q1	q0	q1

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

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

Q = {q₀, q₁, q₂, q₃, q₄, q₅, q₆}

S = q₀

F = {q₅, q₆}

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 = x₀x₁x₂ r₀x₁x₂ r₀r₁r₂x₁x₂

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

r1 = r₀x₁x₂ r₀r₁r₂x₁ r₁r₂x₁x₂ r₁r₂x₁x₂

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

r2 = r₁r₂x₁x₂ r₁x₁x₂ x₀x₁x₂ r₁r₂x₁x₂