В математической логике и информатике формальный язык — это множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.
В теории моделей язык соответствует не языку в информатике, а скорее алфавиту. Язык состоит из множеств символов, функций и отношений вместе с их арностью, а также множество переменных. Каждое из этих множеств может быть бесконечным. Из языка вместе с универсальными логическими символами составляются логические высказывания.
Определение
Формальный язык может быть определён по-разному, например:
Если алфавит задан как {a, b}, а язык L включает в себя все слова над ним, то слово ababba принадлежит L. Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как e, ε или Λ.
Некоторые примеры формальных языков:
Операции
Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что и являются языками, определёнными над некоторым общим алфавитом.
- Конкатенация (сцепление) содержит все слова, удовлетворяющие форме , где — это слово из , а — слово из .
- Пересечение содержит все слова, содержащиеся и в , и в .
- Объединение содержит все слова, содержащиеся или в , или в .
- Дополнение языка содержит все слова алфавита, которые не содержатся в .
- Правое отношение содержит все слова , для которых существует слово в такое, что находидось в .
- Замыкание Клини содержит все слова, которые могут быть записаны в форме , где содержится в и . Следует помнить, что это включает и пустое слово , так как допустимо по условию.
- Обращение содержит обращённые слова из .
- Смешение и содержит все слова, которые могут быть записаны в форме , где и являются такими словами, что связь находится в , а являются такими словами, что находятся в .
Список литературы
- Хопкрофт, Дж., Мотвани, Р., Дж. Ульман. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002 (пер. издания Addison Wesley). ISBN 5-8459-0261-4
- Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г. Теория и реализация языков программирования //М.: МЗ-Пресс, 2006 г., 2-е изд. ISBN 94073-094-9.
- Избранные книги по курсам «Теория и реализация языков программирования» и «Формальные языки трансляций»