Расширенные регулярные выражения: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>]] и, следовательно, является ''труднорешаемой''. | ||
выражений не принадлежит [[классы P и NP|классу <math>{\mathcal NP}</math>]] и, следовательно, | |||
является ''труднорешаемой''. | |||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
Текущая версия от 14:16, 15 июля 2011
Расширенные регулярные выражения (Extended regular expressions) — Расширенное регулярное выражение над алфавитом [math]\displaystyle{ \,\Sigma }[/math] определяется следующим образом:
1) [math]\displaystyle{ e,\emptyset }[/math] и [math]\displaystyle{ \,a }[/math] из [math]\displaystyle{ \,\Sigma }[/math] являются расширенными регулярными выражениями, представляющими соответственно [math]\displaystyle{ \,\{e\} }[/math], пустое множество и [math]\displaystyle{ \,a }[/math];
2) если [math]\displaystyle{ \,E_1 }[/math] и [math]\displaystyle{ \,E_2 }[/math] — расширенные регулярные выражения, представляющие соответственно языки [math]\displaystyle{ \,L_1 }[/math] и [math]\displaystyle{ \,L_2 }[/math], то [math]\displaystyle{ (E_1+E_2), (E_1\cdot E_2), (E_1^*), (E_1\cap E_2) }[/math] и [math]\displaystyle{ (\overline{E_1}) }[/math] — тоже расширенные регулярные выражения, представляющие соответственно языки [math]\displaystyle{ L_1\cup L_2,\ L_1L_2,\ L_{1}^{*},\ L_1\cap L_2 }[/math] и [math]\displaystyle{ \Sigma^*\setminus L_1 }[/math].
Задача пустоты дополнения для расширенных регулярных выражений не принадлежит классу [math]\displaystyle{ {\mathcal NP} }[/math] и, следовательно, является труднорешаемой.
Литература
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.