Русская Википедия:Формальный язык
Форма́льный язы́к в математической логике, информатике и лингвистике — множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.
В теории моделей язык строится из множеств символов, функций и отношений вместе с их арностью, а также множества переменных. Каждое из этих множеств может быть бесконечным. Из языка вместе с универсальными логическими символами составляются логические высказывания.
Определение
Формальный язык может быть определён по-разному, например:
- Простым перечислением слов, входящих в данный язык. Этот способ, в основном, применим для определения конечных языков и языков простой структуры.
- Словами, порождёнными некоторой формальной грамматикой (см. иерархия Хомского).
- Словами, порождёнными регулярным выражением.
- Словами, распознаваемыми некоторым конечным автоматом.
- Словами, порождёнными БНФ-конструкцией.
Например, если алфавит задан как <math>\{a, b\}</math>, а язык <math>L</math> включает в себя все слова над ним, то слово <math>ababba</math> принадлежит <math>L</math>. Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как <math>e</math>, <math>\epsilon</math> или <math>\Lambda</math>.
Некоторые другие примеры формальных языков:
- множество <math>\{ a^n\}</math>, где <math>n</math> — неотрицательное число, а <math>a^{n}</math> означает, что <math>a</math> повторяется <math>n</math> раз;
- множество синтаксически корректных программ в данном языке программирования.
Операции
Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что <math>L_{1}</math> и <math>L_{2}</math> являются языками, определёнными над некоторым общим алфавитом.
- Конкатенация (сцепление) <math>L_{1}L_{2}</math> содержит все слова, удовлетворяющие форме <math>vw</math>, где <math>v</math> — это слово из <math>L_{1}</math>, а <math>w</math> — слово из <math>L_{2}</math>.
- Пересечение <math>L_1 \cap L_2</math> содержит все слова, содержащиеся и в <math>L_1</math>, и в <math>L_{2}</math>.
- Объединение <math>L_1 \cup L_2</math> содержит все слова, содержащиеся в <math>L_{1}</math> или в <math>L_{2}</math>.
- Дополнение языка <math>L_{1}</math> содержит все слова алфавита, которые не содержатся в <math>L_{1}</math>.
- Правое отношение <math>L_{1}/L_{2}</math> содержит все слова <math>v</math>, для которых существует слово <math>w</math> в <math>L_{2}</math> такое, что <math>vw</math> находилось в <math>L_{1}</math>.
- Замыкание Клини <math>L_{1}^{*}</math> содержит все слова, которые могут быть записаны в форме <math>w_{1}w_{2}...w_{n}</math>, где <math>w_{i}</math> содержится в <math>L_{1}</math> и <math>n \ge 0</math>. Следует помнить, что это включает и пустое слово <math>\epsilon</math>, так как <math>n = 0</math> допустимо по условию.
- Обращение <math>L_{1}^{R}</math> содержит обращённые слова из <math>L_{1}</math>.
- Смешение <math>L_{1}</math> и <math>L_{2}</math> содержит все слова, которые могут быть записаны в форме <math>v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}</math>, где <math>n \ge 1</math> и <math>v_{1},...,v_{n}</math> являются такими словами, что связь <math>v_{1}...v_{n}</math> находится в <math>L_{1}</math>, а <math>w_{1},...,w_{n}</math> являются такими словами, что <math>w_{1}...w_{n}</math> находятся в <math>L_{2}</math>.
История
В XVII веке Готфрид Лейбниц представил и описал идею о «characteristica universalis» — универсальном и формальном языке, использующем пиктограммы. В этот период Карл Фридрих Гаусс также занимался проблемой нотацией Гаусса[1].
Готлоб Фреге попытался воплотить идеи Лейбница в системе обозначений, которая была впервые описана в его работе «Шаблон:Нп3» (1879) и более полно разработана в двухтомнике «Шаблон:Нп3» (1893/1903). Эта система описывала «формальный язык чистой логики»[2].
В первой половине XX века были сделаны несколько разработок, имеющих отношение к формальным языкам. Аксель Туэ опубликовал четыре статьи, связанные с понятиями слов и языка, между 1906 и 1914 годами. В последней из них были представлены теории, которые Эмиль Пост позже назвал системами Туэ, и дал первый пример неразрешимой проблемы — проблемы равенства для полугрупп[3]. Пост позже использовал эту статью в своем доказательстве в 1947 году «о том, что проблема слов для полугрупп является рекурсивно неразрешимой»[4], а также разработал каноническую систему для создания формальных языков.
Ноам Хомский создал абстрактное представление формальных и естественных языков, известное как иерархия Хомского[5]. В 1959 году Джон Бэкус разработал форму для описания синтаксиса языка программирования высокого уровня на основе своей работы по созданию Фортрана. Питер Наур был редактором «Доклада об алгоритмическом языке Алгол 60», в котором он использовал форму Бэкуса — Наура для описания формальной части Алгола 60.
См. также
Примечания
Литература
- Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 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.
- Шаблон:НФЭ
- Формальные грамматики и языки. Элементы теории трансляции. Учеб. пос. для студ. 2-го курса. / И. А. Волкова, А. А. Вылиток, Т. В. Руденко. М.: ВМК МГУ, 2009 (на портале ВМК МГУ).
Шаблон:Вс Шаблон:Формальные языки Шаблон:Rq
