Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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> --- регулярные множества в алфавите <math>\Sigma</math>;


(2) если <math>P</math>, <math>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</math>, <math>PQ</math> и <math>P^*</math>;


(3) других регулярных множеств в
:(3) других регулярных множеств в алфавите <math>\,\Sigma</math> нет.
алфавите <math>\Sigma</math> нет.


Используется несколько
Используется несколько
методов задания языков, каждый из которых определяет в
методов задания языков, каждый из которых определяет в
точности регулярные множества. Среди них ---
точности регулярные множества. Среди них
[[регулярные выражения|''регулярные выражения'']], [[автоматная грамматика|''автоматные грамматики'']],
[[регулярные выражения|''регулярные выражения'']], [[автоматная грамматика|''автоматные грамматики'']],
[[праволинейная грамматика|''праволинейные грамматики'']],
[[праволинейная грамматика|''праволинейные грамматики'']],
Строка 27: Строка 22:
==Литература==
==Литература==


[Ахо-Ульман],  
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.


[Касьянов/95]


[[Категория: Теория формальных языков]]
[[Категория: Теория формальных языков]]