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

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

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

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

Определение

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

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

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

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

множество $\{a^{n}\}$ $\{a^{n}\}$ , где $n$ $n$ — неотрицательное число , а $a^{n}$ $a^{{n}}$ означает, что $a$ $a$ повторяется $n$ $n$ раз;
множество синтаксически корректных программ в данном языке программирования .

Операции

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

Конкатенация (сцепление) $L_{1}L_{2}$ $L_{{1}}L_{{2}}$ содержит все слова, удовлетворяющие форме $vw$ $vw$ , где $v$ $v$ — это слово из $L_{1}$ $L_{{1}}$ , а $w$ $w$ — слово из $L_{2}$ $L_{{2}}$ .
Пересечение $L_{1}\cap L_{2}$ $L_{1}\cap L_{2}$ содержит все слова, содержащиеся и в $L_{1}$ $L_{1}$ , и в $L_{2}$ $L_{{2}}$ .
Объединение $L_{1}\cup L_{2}$ $L_{1}\cup L_{2}$ содержит все слова, содержащиеся в $L_{1}$ $L_{{1}}$ или в $L_{2}$ $L_{{2}}$ .
Дополнение языка $L_{1}$ $L_{{1}}$ содержит все слова алфавита, которые не содержатся в $L_{1}$ $L_{{1}}$ .
Правое отношение $L_{1}/L_{2}$ $L_{{1}}/L_{{2}}$ содержит все слова $v$ $v$ , для которых существует слово $w$ $w$ в $L_{2}$ $L_{{2}}$ такое, что $vw$ $vw$ находилось в $L_{1}$ $L_{{1}}$ .
Замыкание Клини $L_{1}^{*}$ $L_{{1}}^{{*}}$ содержит все слова, которые могут быть записаны в форме $w_{1}w_{2}...w_{n}$ $w_{{1}}w_{{2}}...w_{{n}}$ , где $w_{i}$ $w_{{i}}$ содержится в $L_{1}$ $L_{{1}}$ и $n\geq 0$ $n\geq 0$ . Следует помнить, что это включает и пустое слово $\epsilon$ $\epsilon$ , так как $n=0$ $n=0$ допустимо по условию.
Обращение $L_{1}^{R}$ $L_{{1}}^{{R}}$ содержит обращённые слова из $L_{1}$ $L_{{1}}$ .
Смешение $L_{1}$ $L_{{1}}$ и $L_{2}$ $L_{{2}}$ содержит все слова, которые могут быть записаны в форме $v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}$ $v_{{1}}w_{{1}}v_{{2}}w_{{2}}...v_{{n}}w_{{n}}$ , где $n\geq 1$ $n\geq 1$ и $v_{1},...,v_{n}$ $v_{{1}},...,v_{{n}}$ являются такими словами, что связь $v_{1}...v_{n}$ $v_{{1}}...v_{{n}}$ находится в $L_{1}$ $L_{{1}}$ , а $w_{1},...,w_{n}$ $w_{{1}},...,w_{{n}}$ являются такими словами, что $w_{1}...w_{n}$ $w_{{1}}...w_{{n}}$ находятся в $L_{2}$ $L_{{2}}$ .

История

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

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

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

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

См. также

Формальная семантика

Примечания

(неопр.) (январь 1992). Дата обращения: 30 апреля 2021.
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 .
(неопр.) (28 августа 2013). Дата обращения: 30 апреля 2021. 30 апреля 2021 года.
(неопр.) (сентябрь 2001). Дата обращения: 30 апреля 2021.
Jager, Gerhard; Rogers, James (19 July 2012). . Philosophical Transactions of the Royal Society B . 367 (1598): 1956—1970. DOI : . PMC . PMID .

Литература

Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973. — 368 с.
Хопкрофт Дж. , Мотвани Р. , Ульман Дж. Введение в теорию автоматов, языков и вычислений. — М.: Вильямс, 2002 (пер. издания Addison Wesley). — 528 с. — ISBN 5-8459-0261-4
Кревский И. Г., Селивёрстов М. Н., Григорьева К. В. Формальные языки, грамматики и основы построения трансляторов: Учебное пособие / Под ред. А. М. Бершадского . — Пенза: Изд-во Пенз. гос. ун-та, 2002. — 124 с.
Мартыненко Б. К. Языки и трансляции: Учебное пособие. — СПб.: Издательство С.-Петербургского университета, 2003. — 235 с.
Серебряков В. А. , Галочкин М. П., Гончар Д. Р., Фуругян М. Г. — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
Пентус А. Е., Пентус М. Р. Математическая теория формальных языков. — М.: Интернет-университет информационных технологий, Бином. Лаборатория знаний, 2006. — 248 с.
Фомичёв В. С. — Интернет-публикация, 2006.
Б. В. Бирюков. // Новая философская энциклопедия : в 4 т. / пред. науч.-ред. совета В. С. Стёпин . — 2-е изд., испр. и доп. — М. : Мысль , 2010. — 2816 с.
. / И. А. Волкова, А. А. Вылиток, Т. В. Руденко . М.: ВМК МГУ, 2009 (на портале ВМК МГУ) .