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

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

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

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

Определение

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

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

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

Операции

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

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

История

В XVII веке Готфрид Лейбниц представил и описал идею о «characteristica universalis» — универсальном и формальном языке, использующем пиктограммы. В этот период Карл Фридрих Гаусс также занимался проблемой нотацией Гаусса[1].

Готлоб Фреге попытался воплотить идеи Лейбница в системе обозначений, которая была впервые описана в его работе «Begriffsschrift[нем.]» (1879) и более полно разработана в двухтомнике «Grundgesetze der Arithmetik[нем.]» (1893/1903). Эта система описывала «формальный язык чистой логики»[2].

В первой половине XX века были сделаны несколько разработок, имеющих отношение к формальным языкам. Аксель Туэ опубликовал четыре статьи, связанные с понятиями слов и языка, между 1906 и 1914 годами. В последней из них были представлены теории, которые Эмиль Пост позже назвал системами Туэ, и дал первый пример неразрешимой проблемы — проблемы равенства для полугрупп[3]. Пост позже использовал эту статью в своем доказательстве в 1947 году «о том, что проблема слов для полугрупп является рекурсивно неразрешимой»[4], а также разработал каноническую систему для создания формальных языков.

Ноам Хомский создал абстрактное представление формальных и естественных языков, известное как иерархия Хомского[5]. В 1959 году Джон Бэкус разработал форму для описания синтаксиса языка программирования высокого уровня на основе своей работы по созданию Фортрана. Питер Наур был редактором «Доклада об алгоритмическом языке Алгол 60», в котором он использовал форму Бэкуса — Наура для описания формальной части Алгола 60.

См. также

Примечания

  1. In the prehistory of formal language theory: Gauss Languages (январь 1992). Дата обращения: 30 апреля 2021.
  2. Martin Davis. Influences of Mathematical Logic on Computer Science // The universal Turing machine: a half-century survey / Rolf Herken. — Springer, 1995. — P. 290. — ISBN 978-3-211-82637-9.
  3. Thue's 1914 paper: a translation (28 августа 2013). Дата обращения: 30 апреля 2021. Архивировано 30 апреля 2021 года.
  4. Emil Leon Post (сентябрь 2001). Дата обращения: 30 апреля 2021. Архивировано 30 апреля 2021 года.
  5. Jager, Gerhard; Rogers, James (19 July 2012). "Formal language theory: refining the Chomsky hierarchy". Philosophical Transactions of the Royal Society B. 367 (1598): 1956—1970. doi:10.1098/rstb.2012.0077. PMC 3367686. PMID 22688632.

Литература