4194
правки
Регулярные множества: различия между версиями
Материал из WEGA
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Регулярные множества''' ([[Regular sets|''Regular sets'']]) | '''Регулярные множества''' ([[Regular sets|''Regular sets'']]) — класс языков, занимающий | ||
центральное положение по отношению к значительной части теории формальных языков. | центральное положение по отношению к значительной части теории формальных языков. | ||
Пусть <math>\Sigma</math> | Пусть <math>\,\Sigma</math> — некоторый алфавит. | ||
''Регулярное множество в алфавите'' <math>\Sigma</math> определяется | ''Регулярное множество в алфавите'' <math>\,\Sigma</math> определяется | ||
рекурсивно следующим образом: | рекурсивно следующим образом: | ||
(1) пустое множество <math>\emptyset</math>, множество <math>\{e\}</math> состоящее из одной | :(1) пустое множество <math>\emptyset</math>, множество <math>\,\{e\}</math>, состоящее из одной пустой цепочки <math>\,e</math>, а также множество <math>\,\{a\}</math> для каждого элемента <math>\,a\in\Sigma</math> — регулярные множества в алфавите <math>\,\Sigma</math>; | ||
пустой цепочки <math>e</math>, а также множество <math>\{a\}</math>для каждого элемента | |||
<math>a\in\Sigma</math> | |||
(2) если <math>P | :(2) если <math>\,P,\,Q</math> — регулярные множества в алфавите <math>\,\Sigma</math>, то регулярными являются множества <math>\,P\cup Q,\,PQ</math> и <math>\,P^*</math>; | ||
<math>\Sigma</math>, то регулярными являются множества | |||
<math>P\cup Q | |||
(3) других регулярных множеств в | :(3) других регулярных множеств в алфавите <math>\,\Sigma</math> нет. | ||
алфавите <math>\Sigma</math> нет. | |||
Используется несколько | Используется несколько | ||
методов задания языков, каждый из которых определяет в | методов задания языков, каждый из которых определяет в | ||
точности регулярные множества. Среди них | точности регулярные множества. Среди них — | ||
[[регулярные выражения|''регулярные выражения'']], [[автоматная грамматика|''автоматные грамматики'']], | [[регулярные выражения|''регулярные выражения'']], [[автоматная грамматика|''автоматные грамматики'']], | ||
[[праволинейная грамматика|''праволинейные грамматики'']], | [[праволинейная грамматика|''праволинейные грамматики'']], | ||
| Строка 27: | Строка 22: | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
