Словарные функции

Введем начальные понятия:

A = {a₁, …, a_k} – набор букв (алфавит)

a = a₁a₂…a_n – слово (a_i Î A)

l - пустое слово

|a| - длина слова (число букв, из которых состоит слово)

|l| = 0

Свойства:

1) Свойство пустого слова: la = al = a

2) Ассоциативность: (ab)c = a(bc)

3) Некоммутативность: ab ¹ ba

Обозначения:

A­ⁿ – множество всех слов длины n.

- множество всех слов, которые можно составить из букв алфавита А.

Сверхслово – слово, составленное из бесконечного числа букв.

A^w - множество всех сверхслов a₁a₂…

f: A^* ® B^* - словарная функция.

Примеры:

1) f(x) = l

2) f(x) = x

3) f(x₁, …, x_n) = x₂x₃…x_nx₁

4) f(x₁, …, x_n) = x_nx_n-1…x₁ f(сон) = нос

5) A = B = {0, 1} = f(x₁, …, x_n) = x₁, x₁ Ú x₂, x₂ Ú x₃, …, x_n-1 Ú x_n

(Лекция 13)

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

g(a) – состояние, в которое перейдет автомат после подачи сигнала a.

f: A^* ® B^*

При этом

g: A^* ® B^*

Определение. Функция f(x) называется детерминированной, если выполняются условия:

1) |f(a)| = |a|

2) Для любых a, b Î A^* слово f(a) – начало слова f(ab), то есть f(ab) = f(a)g, где g = [по определению] = f_a(b) – остаточная функция для слова a.

Пример:

f_a(b) = a_k Ú b₁, b₁ Ú b₂, …

a_k = 0 Þ f_a(b) = b₁, b₁ Ú b₂, … = g(b)

a_k = 1 Þ f_a(b) = 1, b₁ Ú b₂, … = H(b)

g(b) и H(b) – разные остаточные функции.

Утверждение: Функция остаточная детерминированной есть детерминированная функция.

Доказательство:

Докажем f_a(b) – детерминированная, если f(x) – детерминированная

1) Проверить: | f_a(b)| = |b|.

Доказательство: рассмотрим | f_a(b)| = [так как f - детерминированная] = |ab| = |a| + |b| (1)

С другой стороны: f(ab) = f(a)f_a(b) Þ | f_a(b)| = |f(a)| + |f_a(b)| = [так как f - детерминированная] =

= |a| + |f_a(b)| (2)

Из (1) и (2) следует, что |b| = |f_a(b)|, что и требовалось доказать в первом пункте.

2) Проверим условие f_a(bg) = f_a(b)d

Доказательство: f(abg) = [по 2-му условию детерминируемости функции f] = f(a)f_a(bg) (3)

f(abg) = [f(x, g) - детерминируемая] = f(ab)f_ab(g) (4)

Из (3) и (4) получим , что и требовалось доказать во втором пункте.

Вывод: Мы доказали, что если f – детерминированная, то:

1) f_a - детерминированная

2) (f_a)_b - детерминированная

3)

Определение. Число (r(f)) остаточных функций в данной функции f называется ее весом.

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

Теорема (Критерий автоматности функции)

Функция является автоматной тогда и только тогда, когда она ограниченно детерминированная.

Доказательство:

1) Необходимость. Функция автоматная Þ [по определению] Þ Существует автомат, реализующий ее Þ Строим диаграмму Мура. Число вершин (состояний автомата) конечно, но оно не может быть меньше веса функции Þ вес конечен Þ Функция детерминированная.

2) Достаточность. (Доказать самостоятельно J)

Определение. Функция f: A^w ® B^w называется детерминированной тогда и только тогда, когда выполняются условия:

1) Для любого s ³ 0, s-й символ y(s) слова - однозначно детерминируемая функция первых s символов x(1)x(2)…x(s) слова . То есть в первый момент времени x(1) ® y(1), x(2) ® y(2).

2) Если начала слов и совпадают, то совпадают и начала слов той же длины и . Другими словами, функция f: x₁x₂…x_n ® y₁y₂…y_n - детерминируемая, если y_n – функция от x₁, x₂, …, x_n, но не зависит от последующих (x_n+1, …).

Пример:

j(x(1), x(2), …) = x(2)x(3)…, то есть y(t) = x(t+1), t ³ 1, то есть эта функция детерминируемая, так как y(t) зависит от входного сигнала в следующий момент времени.