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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Расширенные регулярные выражения''' (''Extended regular expressions'') - ''Расширенное рег...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Расширенные регулярные выражения''' (''Extended regular expressions'') -
'''Расширенные регулярные выражения''' (''[[Extended regular expression|Extended regular expressions]]'') ''Расширенное регулярное выражение'' над [[алфавит|алфавитом]]
''Расширенное регулярное выражение'' над алфавитом
<math>\,\Sigma</math> определяется следующим образом:
<math>\Sigma</math> определяется следующим образом:


1) <math>e,\emptyset</math> и <math>a</math> из <math>\Sigma</math> являются расширенными
1) <math>e,\emptyset</math> и <math>\,a</math> из <math>\,\Sigma</math> являются расширенными
регулярными выражениями, представляющими соответственно <math>\{
регулярными выражениями, представляющими соответственно <math>\,\{e\}</math>, пустое множество и <math>\,a</math>;
e\}</math>, пустое множество и <math>a</math>;


2) если <math>E_1</math> и <math>E_2</math> --- расширенные регулярные выражения,
2) если <math>\,E_1</math> и <math>\,E_2</math> расширенные регулярные выражения, представляющие соответственно языки <math>\,L_1</math> и <math>\,L_2</math>, то <math>(E_1+E_2), (E_1\cdot E_2), (E_1^*), (E_1\cap E_2)</math> и <math>(\overline{E_1})</math> тоже расширенные регулярные выражения, представляющие соответственно языки <math>L_1\cup L_2,\ L_1L_2,\ L_{1}^{*},\ L_1\cap L_2</math> и <math>\Sigma^*\setminus L_1</math>.
представляющие соответственно языки <math>L_1</math> и <math>L_2</math>, то
<math>(E_1+E_2), (E_1\cdot E_2), (E_1^*), (E_1\cap E_2)</math> и
<math>(\overline{E_1})</math> --- тоже расширенные регулярные
выражения, представляющие соответственно языки <math>L_1\cup
L_2,\ L_1L_2,\ L_{1}^{*},\ L_1\cap L_2</math> и <math>\Sigma^*\setminus
L_1</math>.


Задача пустоты дополнения для расширенных регулярных
Задача пустоты дополнения для расширенных регулярных выражений не принадлежит [[классы P и NP|классу <math>{\mathcal NP}</math>]] и, следовательно, является ''труднорешаемой''.
выражений не принадлежит классу <math>{\cal NP}</math> и, следовательно,
является ''труднорешаемой''.
==Литература==
==Литература==
[Ахо-Ульман]
 
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.

Навигация