Формальные и неформальные языки
Введение
В информатике и теории языков принято разделять понятия формального и неформального языка. Формальные языки используются для точного описания синтаксиса и структуры данных, программ и протоколов, тогда как неформальные языки — это естественные языки, которыми пользуются люди в повседневном общении. Понимание различий между ними важно для разработки компиляторов, разработки спецификаций и обучения алгоритмическому мышлению.
множество конечных последовательностей символов, составленных из некоторого алфавита \(\Sigma\), и обладающее строгими правилами формирования допустимых последовательностей.
язык естественного общения людей, содержащий нестрогие правила, неоднозначности и элементы контекста, которые трудно формализовать полностью для автоматической обработки.
Алфавит и цепочки
Базовый элемент формального языка — это алфавит, множество символов, из которых строятся цепочки. Алфавит обычно обозначают символом \(\Sigma\). Множество всех возможных цепочек (включая пустую цепочку) над алфавитом называют кліновским замыканием и обозначают \(\Sigma^*\).
Цепочка — это конечная последовательность символов из алфавита. Длину цепочки обычно обозначают как \(|w|\), а пустую цепочку — специальным символом. Операция конкатенации двух цепочек — простое «склеивание» одной за другой; для двух цепочек это можно записать как \(w_1 w_2\).
Кроме множества всех цепочек выделяют также непустое замыкание алфавита, которое содержит все непустые цепочки; оно обозначается как \(\Sigma^+\). Понимание этих базовых понятий необходимо для дальнейшего изучения операций над языками и грамматик.
Операции над формальными языками
Формальные языки как множества цепочек допускают стандартные операции над множествами — объединение, пересечение, дополнение и разность. Объединение двух языков обычно обозначается как, пересечение — как \(L_1 \cap L_2\). Эти операции позволяют строить новые языки из уже известных и изучать их свойства.
Особенно важны операции конкатенации языков и операция Клини (звезда Клини), которая даёт возможность повторять цепочки произвольное число раз. Множество всех склеиваний цепочек из языков и их повторений активно используется при описании регулярных языков и регулярных выражений.
Пример: множество всех цепочек из символов ''a'' и ''b'' может задаваться регулярным выражением \((a|b)^*\) и эквивалентно множеству \(\Sigma^*\) при соответствующем алфавите.
Грамматики и формальные системы
формальная система правил, которая описывает процессы порождения цепочек языка; грамматика обычно задаётся как кортеж \(G=(V,\Sigma,R,S)\), где перечислены множества терминальных и нетерминальных символов, правила переписывания и начальный символ.
Существуют классы грамматик разной мощности — регулярные, контекстно-свободные, контекстно-чувствительные и тьюринг-полные формальные системы. Класс грамматики определяет мощность языка и то, какие вычислительные или автомата́чные модели способны распознавать соответствующие языки.
Процесс выводов (порождающих действий) в грамматике часто обозначают стрелочной нотацией; если из начального символа S выводят цепочку w за конечное число шагов, это записывают как \(S \Rightarrow^* w\). Понимание механики выводов важно для синтаксического анализа и построения парсеров.
Свойства и ограниченности формальных языков
Формальные языки подчиняются ряду теорем и лемм, которые помогают оценивать их мощность и границы применимости. Примером может служить лемма о накачке для регулярных языков и для контекстно-свободных; эти результаты дают условие, которое язык обязан удовлетворять, чтобы быть регулярным или контекстно-свободным. Одно из формальных записаний условий леммы о накачке для регулярных языков можно представить так: \(\exists p\;\forall w\in L\ (|w|\ge p\Rightarrow \exists x,y,z\ (w=xyz\land |xy|\le p\land |y|>0\land \forall i\ge0\;xy^iz\in L))\).
Существуют также тривиальные языки: пустой язык, обозначаемый как \(\varnothing\), и язык, содержащий только пустую цепочку. Эти примеры часто используются в доказательствах и контрпримерах для иллюстрации свойств семейств языков.
Важно помнить, что наличие формального описания не означает простоты обработки — некоторые формально определённые языки требовательны по ресурсам вычисления, требуют сложных автоматов или неразрешимы в общем случае.
Неформальные языки: особенности и сложности
Неформальные языки (естественные языки) содержат многозначность, контекст-зависимость и прагматику, что затрудняет их формализацию. В них часто присутствуют омонимы, синтаксические и семантические неоднозначности, а также эвристические правила, которые люди используют интуитивно. Такие особенности делают полную автоматическую обработку натурального языка сложной задачей.
Тем не менее, методы формализации — лексический и синтаксический анализ, модели на основе грамматик и статистические подходы — позволяют решать множество практических задач: разбор предложений, машинный перевод, анализ тональности и пр. При этом обычно применяются упрощённые формальные модели, которые не покрывают всю полноту естественного языка, но достаточно эффективны в конкретных прикладных задачах.
Пример: в естественном языке фраза «Я видел человека с биноклем» может интерпретироваться двояко: инструмент наблюдения принадлежит говорящему или человеку, которого он видел. Такая двусмысленность трудно устраняется только синтаксическими правилами и требует дополнительного контекста.
Практические примеры и задачи
В практике обучения и разработке алгоритмов полезно рассматривать конкретные примеры формальных языков, их описания и методы распознавания. Один из классических примеров контекстно-свободного языка — множество строк вида \(L=\{a^n b^n \mid n\ge 0\}\), где количество символов ''a'' равно количеству символов ''b''. Этот язык не является регулярным, что демонстрируется, например, с помощью подхода, основанного на лемме о накачке.
Задача: доказать, что язык \(L=\{a^n b^n \mid n\ge 0\}\) не является регулярным. Ключевая идея — предположить регулярность, применить лемму о накачке и получить противоречие при увеличении числа повторений в средней части строки.
Другой тип практических задач — построение регулярных выражений и конечных автоматов для описания простых языков. Регулярные выражения позволяют компактно описывать множества цепочек; например выражение \((a|b)^*\) задаёт множество всех цепочек из символов ''a'' и ''b'' (включая пустую). Перевод между описаниями в виде грамматик, автоматов и регулярных выражений — стандартная учебная задача, полезная для понимания взаимосвязей между различными формальными представлениями.
Наконец, полезно сравнивать формальные модели с реальными приложениями: при проектировании протоколов передачи данных или форматов файлов формальные языки дают точные спецификации, устраняющие неоднозначности, тогда как при работе с пользовательскими текстами приходится комбинировать формальные методы с эвристиками и машинным обучением.