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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Синтаксическое подразделение в рамках формальной системы.

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

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

Определение[править | править код]

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

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

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

Операции[править | править код]

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

  • Конкатенация (сцепление) содержит все слова, удовлетворяющие форме , где  — это слово из , а  — слово из .
  • Пересечение содержит все слова, содержащиеся и в , и в .
  • Объединение содержит все слова, содержащиеся в или в .
  • Дополнение языка содержит все слова алфавита, которые не содержатся в .
  • Правое отношение содержит все слова , для которых существует слово в такое, что находилось в .
  • Замыкание Клини содержит все слова, которые могут быть записаны в форме , где содержится в и . Следует помнить, что это включает и пустое слово , так как допустимо по условию.
  • Обращение содержит обращённые слова из .
  • Смешение и содержит все слова, которые могут быть записаны в форме , где и являются такими словами, что связь находится в , а являются такими словами, что находятся в .

См. также[править | править код]

Литература[править | править код]