§ 5. Язык и алфавит

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

Алфавит — конечное множество символов, используемых для записи сообщений. Символами могут быть буквы, цифры, знаки препинания или специальные обозначения. Например, {0, 1} — алфавит из двух символов. Он задаёт, какие элементы разрешено использовать при составлении последовательностей.

Слово — конечная последовательность символов алфавита. Словом может быть, например, 101 или аба, если соответствующие знаки входят в алфавит. Порядок символов важен: 01 и 10 — разные слова. Это понятие позволяет описывать отдельные сообщения и коды как упорядоченные записи.

Длина слова — количество символов в последовательности. Чтобы её определить, считают каждый символ один раз, в том числе повторяющийся; длину слова w обозначают |w|. Например, |10110| = 5. Длина помогает сравнивать слова и задавать ограничения на их составление.

Язык — множество слов, построенных по правилам данного алфавита. Естественные языки, например русский, служат для общения людей, а формальные языки имеют точно заданные правила построения. Поэтому одинаковый алфавит может использоваться для разных языков: правила определяют, какие последовательности допустимы и как их понимать.

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

Сначала выбирают символы алфавита, а затем соединяют их в последовательности. Если алфавит состоит из 0 и 1, можно получить слова 0, 1, 00, 01 и другие. Перестановка символов обычно меняет слово, потому что слово — не просто набор знаков, а упорядоченная запись. Так, 01 и 10 различаются и по порядку, и как последовательности.

Одного алфавита для определения языка недостаточно: он сообщает, какие символы доступны, но не устанавливает, какие записи разрешены. Правила могут ограничивать длину слова, порядок знаков или их количество. Например, в языке слов, содержащих ровно одну единицу, последовательность 101 подходит, а 111 — нет. Благодаря правилам язык выделяет нужные слова из всех возможных последовательностей.

В естественном языке слова и конструкции связаны с общением людей: смысл зависит от словаря, грамматики и ситуации. Например, слово «лук» может обозначать растение или оружие, и контекст помогает выбрать значение. В формальном языке правила задают точнее, чтобы записи можно было однозначно проверять. Так, запись выражения или команды должна соответствовать установленному синтаксису, то есть правилам построения.

Количество слов фиксированной длины зависит от числа символов в алфавите и числа позиций в слове. Если алфавит содержит k символов, то для каждой из n позиций есть k вариантов; при разрешённых повторениях общее число равно kⁿ. Например, из {а, б, в} для четырёх позиций получаем 3 · 3 · 3 · 3 = 3⁴ = 81 слово. Повторения не уменьшают выбор: на каждой позиции снова доступны все три символа.

Последовательность символов сама по себе не всегда сообщает, что именно она означает. Запись 101 может быть словом двоичного языка, кодом или частью другой записи; её смысл задают правила и ситуация использования. Поэтому совпадение символов ещё не означает совпадения значения. При чтении нужно учитывать, к какому языку относится запись и в каком контексте она дана.

Сравнение естественного и формального языков

Сравнивайте строки таблицы по одному признаку: например, отдельно выясните, как устроены правила или определяется значение. Границы между примерами могут зависеть от задачи, но главное различие — в степени точности правил. Формальный язык позволяет однозначно проверить, допустима ли запись.

Разбор задач

Задача 1. Дан алфавит {0, 1}. Определите длину слова 10110 и запишите ещё два слова длины 3. Сначала проверим, что запись использует только символы алфавита. Затем посчитаем знаки и составим новые слова из тех же двух символов.

1. В слове 10110 пять символов: 1, 0, 1, 1, 0. Значит, его длина равна 5.
2. Для слов длины 3 нужно выбрать ровно три символа из 0 и 1. Например, 000 и 101 подходят, потому что каждый состоит из трёх разрешённых символов.

Ответ: длина 10110 равна 5; примеры слов длины 3 — 000 и 101. Можно было выбрать и другие последовательности, например 011. Главное — использовать только символы заданного алфавита и не менять требуемую длину.

Задача 2. Сколько различных слов длины 4 можно составить из алфавита {а, б, в}, если символы могут повторяться? Под словом здесь понимается любая последовательность из разрешённых знаков. Разберём выбор отдельно для каждой позиции, поскольку повторения разрешены.

1. На первой позиции можно поставить а, б или в — всего 3 варианта. Столько же вариантов есть для второй позиции.
2. Для третьей и четвёртой позиций также доступно по 3 варианта. По правилу умножения общее количество равно 3 · 3 · 3 · 3 = 3⁴ = 81.

Ответ: 81 слово. Например, аааа и вбав входят в этот набор, поскольку в каждой позиции стоит один из трёх символов. Если бы повторения были запрещены, расчёт пришлось бы изменить.

Задача 3. Для алфавита {0, 1} перечислите все слова длины не более 2 и укажите, какие принадлежат языку слов, содержащих ровно одну единицу. Условие «не более 2» включает длины 0, 1 и 2; последовательность длины 0 называют пустым словом и обозначают ε. Сначала перечислим все варианты, затем проверим количество единиц.

1. Длины 0: ε. Длины 1: 0, 1. Длины 2: 00, 01, 10, 11.
2. Считаем единицы в каждой записи. Ровно одна единица есть в словах 1, 01 и 10; в остальных записях условие не выполняется.

Ответ: все слова — ε, 0, 1, 00, 01, 10, 11; языку принадлежат 1, 01 и 10. Пустое слово не содержит ни одной единицы, поэтому оно не подходит. Проверка по условию языка нужна после того, как составлен полный список последовательностей.

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

Алфавит иногда принимают за последовательность символов, потому что его записывают перечислением. Но алфавит — множество, поэтому порядок элементов в записи множества несущественен; в слове порядок, наоборот, важен. Проверка: поменяйте местами элементы в записи алфавита — само множество не изменится. А перестановка знаков в слове обычно даст другое слово.

Слово и язык путают, поскольку оба состоят из символов алфавита. Однако слово — одна последовательность, а язык — множество последовательностей, которые удовлетворяют правилам. Чтобы проверить себя, спросите: речь идёт об одной записи или о совокупности допустимых записей? Например, 101 — слово, а множество слов с ровно одной единицей — язык.

Можно ошибочно считать, что любая последовательность из символов алфавита принадлежит языку. Это неверно: язык ограничивает последовательности своими правилами, хотя все их символы могут быть разрешены алфавитом. Ошибка возникает, когда проверяют только отдельные знаки, а не запись целиком. Сверьте последовательность с условием языка: например, в языке слов с ровно одной единицей запись 111 не подходит.

При подсчёте слов длины n иногда забывают, что символы можно повторять, или умножают k на n. Для каждой позиции есть k вариантов, поэтому число вариантов перемножают n раз и получают kⁿ, а не k · n. Проверка на простом случае помогает заметить ошибку: при двух символах и длине 2 получаются 2 · 2 = 4 слова. Формула kⁿ действует при условии, что повторения разрешены.

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

Для работы с темой нужно понимать, что такое множество, его элемент и конечная последовательность: алфавит является множеством, а слово — последовательностью его элементов. Эти понятия понадобятся при изучении кодирования информации и систем счисления, где сообщения записывают символами выбранного алфавита. В программировании правила языка определяют синтаксис — допустимое построение команд и выражений. Проверка синтаксиса помогает находить неправильные записи ещё до выполнения программы.

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

• Алфавит — множество символов, из которых строят слова.
• Слово — конечная последовательность символов алфавита.
• В слове важен порядок символов.
• Длина слова равна числу входящих в него символов.
• Язык — множество слов, удовлетворяющих его правилам.
• Из алфавита мощности k можно составить kⁿ слов длины n, если повторения разрешены.