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

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

Например, если алфавит задан как {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

Математическая логика | Теория вычислимости

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

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

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