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

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

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

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

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

• множество всех слов над {a, b}
• множество ${\displaystyle \{a^{n}\}}$ , где n — простое число, а ${\displaystyle a^{n}}$  означает, что a повторяется 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}}$ .

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