ABTOMAT = АВТОМАТ?

Помните задачу "101 равно 101?". Ответ неоднозначен, - да, если оба числа записаны в одной системе счисления, - "нет", если числа из разных систем счисления.

Что можно сказать о записи слов? АВТОМАТ и ABTOMAT – это одинаковые слова? Ответ неоднозначен, - да, если оба слова состоят из букв одного алфавита. Ответ "нет", если слова составлены из букв разных алфавитов, таких как кириллица и латиница. В этих алфавитах некоторые буквы совпадают по начертанию, но, тем не менее, – это разные буквы. Слова, составленные из таких букв, как, например, слово "АВТОМАТ", совпадают по начертанию, но это разные слова.

Мы будем изучать тексты, в основе которых лежит алфавит P = {p₁, p₂,… p_k}- конечное, множество символов алфавита, которые иногда называют буквами. Но понятно, что тексты традиционных языков содержат не только буквы, но и цифры, знаки препинания и другие символы, составляющие алфавит языка.

Мы говорили, что изобретение цифр – это великое изобретение, позволившее с помощью конечного числа цифр записывать бесконечное множество чисел.

Не менее важным изобретением было изобретение алфавита, позволившее с помощью конечного множества "букв" алфавита записывать бесконечное множество текстов, например, бессмертный роман Льва Толстого "Война и мир".

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

Пусть P – алфавит. Определим понятие "слово" в алфавите P. Будем называть словом S любую последовательность подряд записанных символов алфавита:

S = s₁ s₂… s_n;

Все символы S – это символы алфавита P. Число символов – n называется длиной слова. Заметьте, определение слова не совпадает с понятием слова в естественных языках. Так роман "Война и мир" - это слово согласно нашему определению, достаточно большое слово, длина которого не менее миллиона.

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

Обозначим через Pⁿ – множество слов длины n.

Справедливо простое, но крайне важное при работе с текстами, утверждение:

Число слов длины n в алфавите P, содержащем k символов равно kⁿ

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

Базис индукции: (n = 1). Слова длины 1 – это символы алфавита, их ровно k, что доказывает справедливость базисного утверждения.

Шаг индукции: Пусть построено множество слов длины m (m >= 1) и число этих слов по индуктивному предположению равно k^m. Построим множество слов длины m + 1. Это построение можно выполнить следующим образом. Каждое слово длины m продолжим одним символом. Поскольку таких символов k, то каждое слово порождает k слов длины m + 1. Отсюда общее число слов длины m + 1 равно k^m * k = k^m+1, что и доказывает справедливость индуктивного шага, следовательно, справедливость утверждения в целом.

Следствие: В алфавите P = {0, 1} число слов длины n равно 2ⁿ

Задача: Постройте множество слов длины 3 в алфавите {0, 1}

Таких слов 8. Вот они:

{000, 001, 010, 011, 100, 101, 110, 111}

Задача: Постройте множество слов длины 4 в алфавите {а, м, п}

Таких слов 3⁴ = 81. Вот они:

{аааа, ааам, ааап, аама, аамп, … мама, … папа, … пппм, пппп}

Мы доказали, что слов длины n равно 2ⁿ. А что если n равно нулю? Cуществуeт ли слово длины 0, - слово, не содержащее символов? Ответ – да, существует. Также как полезна цифра 0, так и пустое слово полезно при работе со словами. Для такого слова вводится специальное обозначение – обычно оно обозначается символом Мы доказали, что слов длины n равно 2ⁿ. А что если n равно нулю? Cуществуeт ли слово длины 0, - слово, не содержащее символов? Ответ – да, существует. Также как полезна цифра 0, так и пустое слово полезно при работе со словами. Для такого слова вводится специальное обозначение – обычно оно обозначается символом ε .

Задача: Сколько слов длины меньше чем 3 в алфавите {0, 1}?

Ответ: Таких слов 7. Вот они:

{ ε, 0, 1, 00, 01, 10, 11}

Приведу без доказательства формулу, позволяющую подсчитать число слов длины меньше чем n в алфавите, содержащем k символов:

N = (kⁿ-1)/(k – 1), справедливую для всех k >1

В алфавите из двух символов N = 2ⁿ - 1

Задачи для самостоятельной работы