Регулярные множества: различия между версиями
Материал из WikiGrapp
KEV (обсуждение | вклад) (Создана новая страница размером '''Регулярные множества''' (''Regular sets'') - класс языков, занимающий цент...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показано 6 промежуточных версий 1 участника) | |||
| Строка 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,Q</math> | :(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> нет. | |||
Используется несколько | Используется несколько | ||
методов задания языков, каждый из которых определяет в | методов задания языков, каждый из которых определяет в | ||
точности регулярные множества. Среди них | точности регулярные множества. Среди них — | ||
[[регулярные выражения|''регулярные выражения'']], [[праволинейная грамматика|''праволинейные грамматики'']], | [[регулярные выражения|''регулярные выражения'']], [[автоматная грамматика|''автоматные грамматики'']], | ||
[[ | [[праволинейная грамматика|''праволинейные грамматики'']], | ||
[[регулярная грамматика|''регулярные грамматики'']], [[конечный автомат|''конечные автоматы'']], | |||
[[детерминированный конечный автомат|''детерминированные конечные автоматы'']]. | [[детерминированный конечный автомат|''детерминированные конечные автоматы'']]. | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
[ | |||
[[Категория: Теория формальных языков]] | |||
Текущая версия от 12:21, 31 августа 2011
Регулярные множества (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.
