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

Материал из Википедии — свободной энциклопедии

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

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

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

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

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

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

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

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

Конкатенация (сцепление) $L 1 L 2$ содержит все слова, удовлетворяющие форме $v w$ , где $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$ такое, что $v w$ находидось в $L 1$ .
Замыкание Клини $L_{1}^{*}$ содержит все слова, которые могут быть записаны в форме $w 1 w 2 ... w n$ , где $w i$ содержится в $L 1$ и $n \ge 0$ . Следует помнить, что это включает и пустое слово $ε$ , так как $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$ .

[править] Другие значения

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

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