正規言語を記述する正規表現Rが与えられます (派手な後方参照はありません)。Rで記述されたものを除くすべての単語の言語を記述する正規表現R*を構築するアルゴリズム的な方法はありますか? ウィキペディアが言うように、それは可能であるはずです：
正規言語は、さまざまな操作の下で閉じられます。つまり、言語KとLが正規である場合、次の操作の結果も同様です: […] 補数¬L
たとえば、アルファベット{a,b,c} が与えられた場合、言語(abc*)+の逆は(a|(ac|b|c).*)?
DPenner がコメントで既に指摘しているように、正規表現の逆数は元の表現より指数関数的に大きくなる可能性があります。これにより、正規表現の反転は、検索目的で否定的な部分式構文を実装するのに適していません。正規表現マッチングのO(n*m)ランタイム特性 ( nは正規表現のサイズ、mは入力の長さ) を保持し、部分式の否定を許可するアルゴリズムはありますか?
残念ながら、コメントで nhahdtdh が提供した回答は、(これまでのところ) 私たちができる限り良いものです。特定の正規表現がすべての文字列を生成するかどうかは、PSPACE 完全です。NP の問題はすべて PSPACE 完全であるため、普遍性の問題を効率的に解決するには、P=NP が必要です。
あなたの問題に対する効率的な解決策があれば、普遍性の問題を解決できますか? 確かにそうするでしょう。
「正規表現が与えられた場合、空のセットを生成するか」という問題はかなり単純であることに注意してください。
{}は空のセットを生成します。(r + s)との両方で空集合rをs生成し、空集合を生成します。(rs)rまたは空のセットをs生成する場合は、空のセットを生成します。基本的に、正規表現が空のセットを生成するかどうかを判断するのは非常に簡単です。正規表現の評価を開始するだけです。
(上記の手順は出力の長さに関しては効率的ですが、出力の長さが入力の長さよりも多項式を超えて高速である場合、入力の長さに関しては効率的ではない可能性があることに注意してください。ただし、その場合は、とにかく同じ結果が得られます。つまり、特定の入力から指数関数的に長い出力を生成するには、指数関数的に多くのステップが必要になるため、アルゴリズムは実際には効率的ではありません)。
ウィキペディアによると: ... 特定のセットに一致する正規表現が少なくとも 1 つ存在する場合、そのような式は無限に存在します。このステートメントから、R によって記述されたものを除くすべての単語の言語を記述する無限の数の表現があると推測できます。
繰り返しますが、(@nhahtdh も説明しようとしたように) この問題に対処する最も簡単なアルゴリズムは、正規表現言語自体のコンテキストの外に評価の範囲を拡張することです。つまり、元の正規表現を使用して、除外する文字列(使用する有限のサブセットを表す)を照合し、一致に失敗した場合は (他の可能性の無限のセットから)実際の一致として扱います。したがって、一致の結果が負の場合、候補文字列は有効なソリューションのサブセットです。