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

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

Синтаксическое подразделение в рамках формальной системы.

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

ОпределениеПравить

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

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

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

ОперацииПравить

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

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

См. такжеПравить

ЛитератураПравить