Регулярные множества

Материал из WikiGrapp
(перенаправлено с «Регулярное множество»)
Перейти к:навигация, поиск

Регулярные множества (Regular sets) — класс языков, занимающий центральное положение по отношению к значительной части теории формальных языков.

Пусть \,\Sigma — некоторый алфавит. Регулярное множество в алфавите \,\Sigma определяется рекурсивно следующим образом:

(1) пустое множество \emptyset, множество \,\{e\}, состоящее из одной пустой цепочки \,e, а также множество \,\{a\} для каждого элемента \,a\in\Sigma — регулярные множества в алфавите \,\Sigma;
(2) если \,P,\,Q — регулярные множества в алфавите \,\Sigma, то регулярными являются множества \,P\cup Q,\,PQ и \,P^*;
(3) других регулярных множеств в алфавите \,\Sigma нет.

Используется несколько методов задания языков, каждый из которых определяет в точности регулярные множества. Среди них — регулярные выражения, автоматные грамматики, праволинейные грамматики, регулярные грамматики, конечные автоматы, детерминированные конечные автоматы.

Литература

  • Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.