regex - 文字列のセットを受け入れる正規表現 A を、A が一致する文字列のすべてのプレフィックスを受け入れる正規表現に変換します

Question

正規表現 A が与えられた場合、A が受け入れるすべての文字列と文字列のプレフィックスを受け入れる別の正規表現 B に変換する方法はありますか。

たとえば、 /apple/ が指定された正規表現である場合、それを /a|ap|app|appl|apple/ に変換する一般的な方法はありますか?

Answer 1

正式な正規表現(つまり、正規言語を記述する正規表現)について話している場合は、正規表現をプレフィックスを受け入れるものに変換する手順を次に示します。

どの正規表現にもDFAがあります。のDFAは次のとおりです/apple/（失敗状態への移行は省略されています）：

この DFA によって受け入れられる文字列のプレフィックスに一致する DFA を生成するには、状態が元の DFA の受け入れ状態につながるパスにある場合、状態を受け入れ状態に変換します。

DFA から正規表現を読み取る方法はいくつかあります。状態除去手法を使用すると、次の DFA に到達します。

これは、正規表現/a|ap|app|appl|apple|/に空の文字列を加えたものに対応します (空の文字列は正規表現のプレフィックスであるため)。

このapple例は簡単ですが、これと同じ手法をより複雑な正規表現に使用できます。たとえば、次のように考えて/(00)*1(00|1)*/ください。

この DFA は文字列を受け入れます00100が、受け入れません0010101。適切な状態を最終状態に変換し、2 つの同一の状態を結合すると、次のようになります。

これは、

/(00)*(0?|1(1|00)*0?)/そこから、空の文字列を含む正規表現を読み取ることができます。

この正規表現は、元の DFA を失敗状態に移行させるため拒否し00101ますが、'0' と '00' を受け入れます。これらの文字列は元の DFA を失敗状態にしないためです。

Answer 2

一般化された方法で何を意味するかによって異なります。

\b(a(p?(p?(l?(e?)))))\b

編集：加算の背後にある前向きな見方はより良い解決策を表しますが、それは完全に正規表現マシンの実装に依存します.