regex - 逆に適用された正規表現は同じ一致を生成しますか？

Question

いくつかのテキストとそれに一致する正規表現があるとします。質問：同じ式をテキストに逆方向に適用した場合（最後の文字から最初の文字まで）、それでも一致しますか？

正規表現----->テキスト

xereg-？-> txet

実際にはうまくいくように見えますが、問題はむしろ一般的なケースについて理論が何を言っているかについてです。

Answer 1

クリーネ閉包を使用する場合ではありません。正規表現を逆にすると、無効な正規表現または別のパターンに一致する正規表現になります。

• ab*-> *ba（無効な構文）
• a*b-> b*a（最初のものは一致しますが一致aaabしませんabbbが、2番目のものは一致しますが一致bbbaしませんbaaa）

一方、正規表現が与えられると、逆の文字列に一致する正規表現を生成するアルゴリズムを設計することは可能であると確信しています。次の再帰的アルゴリズムが機能するはずです（rが正規表現の場合、rev（r）は逆の文字列に一致する正規表現を意味します）。

• rが単一のシンボルxの場合、rev（r）=x。
• rが和集合A|Bの場合、rev（r）= rev（A）| rev（B）。
• rが連結ABの場合、rev（r）= rev（B）rev（A）。
• rがクリーネ閉包A*の場合、rev（r）= rev（A）*。

Answer 2

一般的な原因は、

たとえば、正規表現

ab

一致します

ab

だがしかし

ba

どうして一般的なケースはそうあるべきだと思いますか？

同様に逆の文字列に一致する正規表現があります

[a|b]*

一致します

ab 

と

ba

Answer 3

regexとのxeger両方がテキストで同じ一致を生成する場合は次のとおりです。

1. regex回文である単純な（原子）パターンです。例えば、abcba
2. regexは可換関数（たとえば）を使用するいくつかの原子パターンで構成されており、orそれらの個々の原子パターンを逆にすることはありません。もしそうなら、それらも回文であるはずです。たとえば、adef|bd881|cdavrアトミックコンポーネントを逆にしない場合、またはアトミックコンポーネント[aba|defed]を逆にする場合。

Answer 4

一般的には間違いなく「いいえ」と言いますが、それは実際には表現の複雑さに依存します。

単純な（サブ）式を逆にする必要があるだけでなく、該当する場合は、どの正規表現でも簡単に「逆」にできない、より複雑なものも考慮する必要があるためです。繰り返し演算子、怠惰と。貪欲、または逆参照と見回し、数量詞と修飾子…–このチュートリアルなどで説明されている項目？

おそらく、そのような「逆転」に関するより具体的な例や問題がある場合は、より適切な答えを考えることができます。