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

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

Например, если алфавит задан как {a, b}, а язык L включает в себя все слова над ним, то слово ababba принадлежит L.

Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как e, ε или Λ.

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

• множество всех слов над {a, b}
• множество <math>\{ a^n\}</math>, где n — простое число, а <math>a^{n}</math> означает, что a повторяется n раз
• множество синтаксически корректных программ в данном языке программирования

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

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

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

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

Другие значения

Следует помнить, что мы можем говорить о формальном языке во многих контекстах (научном, юридическом, лингвистическом и других), подразумевая способ выражения более осторожный и аккуратный или же более манерный, чем повседневная речь. Смысл формального языка, подразумеваемый здесь, соответствует его определению в теории формальных языков.

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

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

• Хопкрофт, Дж., Мотвани, Р., Дж. Ульман (2002). Введение в теорию автоматов, языков и вычислений. Addison Wesley. ISBN 5-8459-0261-4