WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте
Синтаксическое подразделение в рамках формальной системы.

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

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

Определение

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

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

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

Операции

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

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

См. также

Литература

  • Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 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.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии