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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

Операции[править | править вики-текст]

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

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

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

Литература[править | править вики-текст]

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