Формальный язык

Не следует путать с формальным стилем речи.

Форма́льный язы́к в математической логике, информатике и лингвистике — множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.

Синтаксическое подразделение в рамках формальной системы.

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

Определение

Формальный язык может быть определён по-разному, например:

• Простым перечислением слов, входящих в данный язык. Этот способ, в основном, применим для определения конечных языков и языков простой структуры.
• Словами, порождёнными некоторой формальной грамматикой (см. иерархия Хомского).
• Словами, порождёнными регулярным выражением.
• Словами, распознаваемыми некоторым конечным автоматом.
• Словами, порождёнными БНФ-конструкцией.

Например, если алфавит задан как ${\displaystyle \{a,b\}}$, а язык ${\displaystyle L}$ включает в себя все слова над ним, то слово ${\displaystyle ababba}$ принадлежит ${\displaystyle L}$. Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как ${\displaystyle e}$, ${\displaystyle \epsilon }$ или ${\displaystyle \Lambda }$.

Некоторые другие примеры формальных языков:

• множество ${\displaystyle \{a^{n}\}}$, где ${\displaystyle n}$ — неотрицательное число, а ${\displaystyle a^{n}}$ означает, что ${\displaystyle a}$ повторяется ${\displaystyle n}$ раз;
• множество синтаксически корректных программ в данном языке программирования.

Операции

Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$ являются языками, определёнными над некоторым общим алфавитом.

• Конкатенация (сцепление) ${\displaystyle L_{1}L_{2}}$ содержит все слова, удовлетворяющие форме ${\displaystyle vw}$, где ${\displaystyle v}$ — это слово из ${\displaystyle L_{1}}$, а ${\displaystyle w}$ — слово из ${\displaystyle L_{2}}$.
• Пересечение ${\displaystyle L_{1}\cap L_{2}}$ содержит все слова, содержащиеся и в ${\displaystyle L_{1}}$, и в ${\displaystyle L_{2}}$.
• Объединение ${\displaystyle L_{1}\cup L_{2}}$ содержит все слова, содержащиеся в ${\displaystyle L_{1}}$ или в ${\displaystyle L_{2}}$.
• Дополнение языка ${\displaystyle L_{1}}$ содержит все слова алфавита, которые не содержатся в ${\displaystyle L_{1}}$.
• Правое отношение ${\displaystyle L_{1}/L_{2}}$ содержит все слова ${\displaystyle v}$, для которых существует слово ${\displaystyle w}$ в ${\displaystyle L_{2}}$ такое, что ${\displaystyle vw}$ находилось в ${\displaystyle L_{1}}$.
• Замыкание Клини ${\displaystyle L_{1}^{*}}$ содержит все слова, которые могут быть записаны в форме ${\displaystyle w_{1}w_{2}...w_{n}}$, где ${\displaystyle w_{i}}$ содержится в ${\displaystyle L_{1}}$ и ${\displaystyle n\geq 0}$. Следует помнить, что это включает и пустое слово ${\displaystyle \epsilon }$, так как ${\displaystyle n=0}$ допустимо по условию.
• Обращение ${\displaystyle L_{1}^{R}}$ содержит обращённые слова из ${\displaystyle L_{1}}$.
• Смешение ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$ содержит все слова, которые могут быть записаны в форме ${\displaystyle v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}}$, где ${\displaystyle n\geq 1}$ и ${\displaystyle v_{1},...,v_{n}}$ являются такими словами, что связь ${\displaystyle v_{1}...v_{n}}$ находится в ${\displaystyle L_{1}}$, а ${\displaystyle w_{1},...,w_{n}}$ являются такими словами, что ${\displaystyle w_{1}...w_{n}}$ находятся в ${\displaystyle L_{2}}$.

История

В XVII веке Готфрид Лейбниц представил и описал идею о «characteristica universalis» — универсальном и формальном языке, использующем пиктограммы. В этот период Карл Фридрих Гаусс также занимался проблемой нотацией Гаусса^[1].

Готлоб Фреге попытался воплотить идеи Лейбница в системе обозначений, которая была впервые описана в его работе «Begriffsschrift^[нем.]» (1879) и более полно разработана в двухтомнике «Grundgesetze der Arithmetik^[нем.]» (1893/1903). Эта система описывала «формальный язык чистой логики»^[2].

В первой половине XX века были сделаны несколько разработок, имеющих отношение к формальным языкам. Аксель Туэ опубликовал четыре статьи, связанные с понятиями слов и языка, между 1906 и 1914 годами. В последней из них были представлены теории, которые Эмиль Пост позже назвал системами Туэ, и дал первый пример неразрешимой проблемы — проблемы равенства для полугрупп^[3]. Пост позже использовал эту статью в своём доказательстве в 1947 году «о том, что проблема слов для полугрупп является рекурсивно неразрешимой»^[4], а также разработал каноническую систему для создания формальных языков.

Ноам Хомский создал абстрактное представление формальных и естественных языков, известное как иерархия Хомского^[5]. В 1959 году Джон Бэкус разработал форму для описания синтаксиса языка программирования высокого уровня на основе своей работы по созданию Фортрана. Питер Наур был редактором «Доклада об алгоритмическом языке Алгол 60», в котором он использовал форму Бэкуса — Наура для описания формальной части Алгола 60.

См. также

• Формальная семантика