Регулярные множества: различия между версиями
KEV (обсуждение | вклад) (Создана новая страница размером '''Регулярные множества''' (''Regular sets'') - класс языков, занимающий цент...) |
(нет различий)
|
Версия от 17:11, 27 апреля 2009
Регулярные множества (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 }[/math], [math]\displaystyle{ PQ }[/math] и [math]\displaystyle{ P^* }[/math];
(3) других регулярных множеств в алфавите [math]\displaystyle{ \Sigma }[/math] нет.
Используется несколько методов задания языков, каждый из которых определяет в точности регулярные множества. Среди них --- регулярные выражения, праволинейные грамматики, регулярные грамматики, конечные автоматы, детерминированные конечные автоматы.
Литература
[Ахо-Ульман],
[Касьянов/95]