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

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

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

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

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

Определение

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

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

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

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

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

Операции

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

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

См. также

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

Литература

• Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 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 с.