Регулярные множества: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 10: Строка 10:
<math>a\in\Sigma</math> --- регулярные множества в алфавите <math>\Sigma</math>;
<math>a\in\Sigma</math> --- регулярные множества в алфавите <math>\Sigma</math>;


(2) если <math>P,Q</math> --- регулярные множества в алфавите
(2) если <math>P</math>, <math>Q</math> --- регулярные множества в алфавите
<math>\Sigma</math>, то регулярными являются множества
<math>\Sigma</math>, то регулярными являются множества
<math>P\cup Q</math>, <math>PQ</math> и <math>P^*</math>;
<math>P\cup Q</math>, <math>PQ</math> и <math>P^*</math>;
Строка 20: Строка 20:
методов задания языков, каждый из которых определяет в
методов задания языков, каждый из которых определяет в
точности регулярные множества. Среди них ---
точности регулярные множества. Среди них ---
[[регулярные выражения|''регулярные выражения'']], [[праволинейная грамматика|''праволинейные грамматики'']],
[[регулярные выражения|''регулярные выражения'']], [[автоматная грамматика|''автоматные грамматики'']],
[[праволинейная грамматика|''праволинейные грамматики'']],
[[регулярная грамматика|''регулярные грамматики'']], [[конечный автомат|''конечные автоматы'']],
[[регулярная грамматика|''регулярные грамматики'']], [[конечный автомат|''конечные автоматы'']],
[[детерминированный конечный автомат|''детерминированные конечные автоматы'']].
[[детерминированный конечный автомат|''детерминированные конечные автоматы'']].

Версия от 22:33, 3 июня 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 }[/math], [math]\displaystyle{ 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]