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

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

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

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

Определение

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

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

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

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

• множество всех слов над {a, b}
• множество $\{ 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$. Следует помнить, что это включает и пустое слово $\epsilon$, так как $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}$.

Список литературы

• Хопкрофт, Дж., Мотвани, Р., Дж. Ульман. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002 (пер. издания Addison Wesley). ISBN 5-8459-0261-4
• Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г. Теория и реализация языков программирования //М.: МЗ-Пресс, 2006 г., 2-е изд. ISBN 94073-094-9.
• Избранные книги по курсам «Теория и реализация языков программирования» и «Формальные языки трансляций»