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

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

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

(1) пустое множество [math]\displaystyle{ \emptyset }[/math], множество [math]\displaystyle{ \,\{e\} }[/math], состоящее из одной пустой цепочки [math]\displaystyle{ \,e }[/math], а также множество [math]\displaystyle{ \,\{a\} }[/math] для каждого элемента [math]\displaystyle{ \,a\in\Sigma }[/math] — регулярные множества в алфавите [math]\displaystyle{ \,\Sigma }[/math];

(2) если [math]\displaystyle{ \,P,\,Q }[/math] — регулярные множества в алфавите [math]\displaystyle{ \,\Sigma }[/math], то регулярными являются множества [math]\displaystyle{ \,P\cup Q,\,PQ }[/math] и [math]\displaystyle{ \,P^* }[/math];

(3) других регулярных множеств в алфавите [math]\displaystyle{ \,\Sigma }[/math] нет.

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

Литература

• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.

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