Слово

Определения и обозначения

Алфавит — конечное множество символов, из которых составляются слова. Например, {А, Б, В} задаёт три допустимые буквы. Сначала указывают алфавит, чтобы точно знать, какие символы разрешено использовать.

Буква — один символ, принадлежащий данному алфавиту. В алфавите {0, 1} буквами будут 0 и 1, а буква 2 ему не принадлежит. Это понятие помогает проверять каждую позицию будущего слова.

Слово — конечная последовательность букв выбранного алфавита. Буквы в последовательности расположены в определённом порядке, например АБА. Такое определение допускает и обычные слова, и наборы символов без привычного смысла.

Длина слова — количество букв в этой последовательности. Слово КОКОС имеет длину 5, потому что в нём пять позиций, а пустое слово не содержит букв и имеет длину 0. Пустое слово часто обозначают специальным символом ε.

Как это устроено

Сначала задают алфавит, потому что без списка допустимых букв нельзя однозначно проверить последовательность. Например, 012 является словом алфавита {0, 1, 2}, а 013 — нет, поскольку символ 3 запрещён. Одна и та же запись может быть словом одного алфавита и не быть словом другого.

Слово образуется последовательным выбором букв и их расположением по позициям. Если поменять местами буквы, изменится порядок, а значит, получится другая последовательность: АБ и БА не совпадают. Даже когда обе последовательности состоят из одинаковых букв, порядок различает их.

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

Чтобы найти начало слова, смотрят на его первую позицию, а конец находится на последней позиции. Позиции удобно нумеровать слева направо: в слове КОКОС К стоит на 1-й позиции, О — на 2-й, К — на 3-й, О — на 4-й, С — на 5-й. Так можно быстро определить букву с нужным номером.

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

Основные понятия темы «Слово»

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

Разбор задач

Задача 1. Дан алфавит {0, 1, 2}. Определим, какие из последовательностей 012, 2102 и 013 являются его словами. Для каждой записи нужно отдельно проверить все символы.

1. В 012 встречаются 0, 1 и 2, и все они входят в алфавит.
2. В 2102 используются только 2, 1 и 0, причём повторение 2 разрешено.
3. В 013 есть символ 3, которого в заданном алфавите нет.

Ответ: 012 и 2102 являются словами, а 013 не является. Повторяющийся символ сам по себе не нарушает правила.

Задача 2. Для слова КОКОС найдём длину, буквы на первой и четвёртой позициях и число повторений О. Сначала пронумеруем все позиции слева направо.

1. Получаем запись: 1 — К, 2 — О, 3 — К, 4 — О, 5 — С.
2. Всего позиций пять, поэтому длина слова равна 5.
3. На первой позиции стоит К, на четвёртой — О, а буква О встречается на позициях 2 и 4.

Ответ: длина КОКОС равна 5, первая буква К, четвёртая буква О, число повторений О равно 2. При подсчёте длины обе буквы О учитываются.

Задача 3. Составим все слова длины 3 из букв {А, Б}, содержащие ровно две буквы А. Нужно расставить две А и одну Б по трём позициям.

1. Буква Б может стоять на первой позиции: БАА.
2. Если Б стоит на второй позиции, получается АБА.
3. Если Б стоит на третьей позиции, получается ААБ.

Ответ: получаются слова БАА, АБА и ААБ, всего 3 слова. Они различны, потому что буква Б занимает разные позиции.

Типичные ошибки

Считать словом любую последовательность. Ошибка возникает, если не проверить алфавит и принять 013 за слово алфавита {0, 1, 2}. Для самопроверки просмотрите каждый символ и найдите его среди допустимых.

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

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

Забывать о пустом слове. Иногда отсутствие символов ошибочно принимают за одну позицию. Проверьте определение: пустое слово содержит 0 букв, значит, его длина равна 0.

Связь с другими темами

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

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

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

Что запомнить

• Алфавит задаёт допустимые символы.
• Слово — упорядоченная конечная последовательность букв алфавита.
• Порядок букв важен.
• Буквы в слове могут повторяться.
• Длина слова равна числу его позиций.
• Пустое слово не содержит букв и имеет длину 0.