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

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


Строка 16: Строка 16:


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

Версия от 15:59, 15 января 2010

Расширенные регулярные выражения (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] и, следовательно, является труднорешаемой.

Литература

[Ахо-Ульман]