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

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

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

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

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

Например, если алфавит задан как ${\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.

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

• Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973. — 368 с.
• Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. — М.: Вильямс, 2002 (пер. издания Addison Wesley). — 528 с. — ISBN 5-8459-0261-4
• Кревский И. Г., Селивёрстов М. Н., Григорьева К. В. Формальные языки, грамматики и основы построения трансляторов: Учебное пособие / Под ред. А. М. Бершадского. — Пенза: Изд-во Пенз. гос. ун-та, 2002. — 124 с.
• Мартыненко Б. К. Языки и трансляции: Учебное пособие. — СПб.: Издательство С.-Петербургского университета, 2003. — 235 с.
• Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
• Пентус А. Е., Пентус М. Р. Математическая теория формальных языков. — М.: Интернет-университет информационных технологий, Бином. Лаборатория знаний, 2006. — 248 с.
• Фомичёв В. С. Формальные языки, грамматики и автоматы: Курс лекций — Интернет-публикация, 2006.
• Б. В. Бирюков. Формализованный язык // Новая философская энциклопедия : в 4 т. / пред. науч.-ред. совета В. С. Стёпин. — 2-е изд., испр. и доп. — М. : Мысль, 2010. — 2816 с.
• Формальные грамматики и языки. Элементы теории трансляции. Учеб. пос. для студ. 2-го курса. / И. А. Волкова, А. А. Вылиток, Т. В. Руденко. М.: ВМК МГУ, 2009 (на портале ВМК МГУ).

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