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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Регулярные множества''' (''Regular sets'') - класс языков, занимающий цент...)
 
Нет описания правки
 
(не показано 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> --- регулярные множества в алфавите <math>\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</math>, <math>PQ</math> и <math>P^*</math>;


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


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


==Литература==
==Литература==


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


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

Текущая версия от 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.