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

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

Определение

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

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

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

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

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

Операции

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

• Конкатенация (сцепление) содержит все слова, удовлетворяющие форме , где — это слово из , а — слово из .
• Пересечение содержит все слова, содержащиеся и в , и в .
• Объединение содержит все слова, содержащиеся или в , или в .
• Дополнение языка содержит все слова алфавита, которые не содержатся в .
• Правое отношение содержит все слова , для которых существует слово в такое, что находидось в .
• Замыкание Клини содержит все слова, которые могут быть записаны в форме , где содержится в и . Следует помнить, что это включает и пустое слово , так как допустимо по условию.
• Обращение содержит обращённые слова из .
• Смешение и содержит все слова, которые могут быть записаны в форме , где и являются такими словами, что связь находится в , а являются такими словами, что находятся в .

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

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