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

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

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

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

Определение

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

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

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

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

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

Операции

Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что $L_1$ и $L_2$ являются языками, определёнными над некоторым общим алфавитом.

• Конкатенация (сцепление) $L_1{L}_2$ содержит все слова, удовлетворяющие форме $vw$, где $v$ — это слово из $L_1$, а $w$ — слово из $L_2$.
• Пересечение $L_1\cap L_2$ содержит все слова, содержащиеся и в $L_1$, и в $L_2$.
• Объединение $L_1\cup L_2$ содержит все слова, содержащиеся в $L_1$ или в $L_2$.
• Дополнение языка $L_1$ содержит все слова алфавита, которые не содержатся в $L_1$.
• Правое отношение $L_1/L_2$ содержит все слова $v$, для которых существует слово $w$ в $L_2$ такое, что $vw$ находилось в $L_1$.
• Замыкание Клини $L_1^{*}$ содержит все слова, которые могут быть записаны в форме $w_1{w}_2...w_n$, где $w_i$ содержится в $L_1$ и $n\ge 0$. Следует помнить, что это включает и пустое слово $ϵ$, так как $n=0$ допустимо по условию.
• Обращение $L_1^R$ содержит обращённые слова из $L_1$.
• Смешение $L_1$ и $L_2$ содержит все слова, которые могут быть записаны в форме $v_1{w}_1{v}_2{w}_2...v_n{w}_n$, где $n\ge 1$ и $v_1,...,v_n$ являются такими словами, что связь $v_1...v_n$ находится в $L_1$, а $w_1,...,w_n$ являются такими словами, что $w_1...w_n$ находятся в $L_2$.

История

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

Готлоб Фреге попытался воплотить идеи Лейбница в системе обозначений, которая была впервые описана в его работе «Шаблон:Нп3» (1879) и более полно разработана в двухтомнике «Шаблон:Нп3» (1893/1903). Эта система описывала «формальный язык чистой логики».

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

Ноам Хомский создал абстрактное представление формальных и естественных языков, известное как иерархия Хомского. В 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.
• Шаблон:НФЭ
• Формальные грамматики и языки. Элементы теории трансляции. Учеб. пос. для студ. 2-го курса. / И. А. Волкова, А. А. Вылиток, Т. В. Руденко. М.: ВМК МГУ, 2009 (на портале ВМК МГУ).