リテラル、正と負の文字クラス、順序付けられた代替、貪欲な量指定子?、*、および+、および非貪欲な量指定子??、 、および をサポートする正規表現言語がある*?とし+?ます。(これは基本的に、後方参照、ルックアラウンド アサーション、またはその他のより複雑な部分を含まない PCRE のサブセットです。) 順序付けられた交互を順序付けられていない交互に置き換えると、この形式主義の表現力が低下しますか?
(順序付けられていない交替 --- 「順序付けられていない選択」とも呼ばれる --- は L(S|T) = L(S) + L(T) であり、順序付けられた交替は L(S|T) = L である) (S) + (L(T) - { L(T) の a : a が L(S) の b を拡張する }). 具体的には、パターンは文字列とa|aa一致し、交互が順序付けられていない場合にのみ、交互が注文しています。）aaaa
別の言い方をすれば、順序付けられた交替を含むパターン S が与えられた場合、そのパターンを、順序付けられた交替を含まない同等のパターン T に書き換えることができますか (ただし、代わりに順序付けされていない交替が含まれる可能性があります)。
この質問が文献で検討されている場合は、誰でも提供できる参考文献をいただければ幸いです。拡張正規表現形式の表現力に関する理論的な研究はほとんど見つけることができませんでした (後方参照がどのように通常の言語から文脈自由文法に移行するかについての通常の事柄を超えて)。