Формальный язык
[править]
Материал из Википедии — свободной энциклопедии
Эта версия страницы ожидает проверки и может отличаться от последней подтверждённой, проверенной 1 апреля 2010.
Не следует путать с формальным стилем речи.

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

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

Прошивка магнитолы Geely Atlas Прошивка магнитолы Geely Coolray Прошивка магнитолы Geely Atlas Pro Прошивка магнитолы Geely Tugella Формальный язык может быть определен по-разному, например:

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

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

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

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

[править] Операции

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

Конкатенация (сцепление) L1L2 содержит все слова, удовлетворяющие форме vw, где v — это слово из L1, а w — слово из L2.
Пересечение L_1 \cap L_2 содержит все слова, содержащиеся и в L1, и в L2.
Объединение L_1 \cup L_2 содержит все слова, содержащиеся или в L1, или в L2.
Дополнение языка L1 содержит все слова алфавита, которые не содержатся в L1.
Правое отношение L1 / L2 содержит все слова v, для которых существует слово w в L2 такое, что vw находидось в L1.
Замыкание Клини L_{1}^{*} содержит все слова, которые могут быть записаны в форме w1w2...wn, где wi содержится в L1 и n \ge 0. Следует помнить, что это включает и пустое слово ε, так как n = 0 допустимо по условию.
Обращение L_{1}^{R} содержит обращенные слова из L1.
Смешение L1 и L2 содержит все слова, которые могут быть записаны в форме v1w1v2w2...vnwn, где n \ge 1 и v1,...,vn являются такими словами, что связь v1...vn находится в L1, а w1,...,wn являются такими словами, что w1...wn находятся в L2.