Расширенные регулярные выражения

Расширенные регулярные выражения (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.