ルックアラウンドは、正規表現でマッチングできる言語に影響を与えますか？

質問

最近の正規表現エンジンには、その機能がなければマッチしないような言語にもマッチさせることができるものがあります。例えば、後方参照を使用した次の正規表現は、それ自体を繰り返す単語で構成されるすべての文字列の言語にマッチします。 (.+)\1 . この言語は正規表現ではないので、後方参照を使用しない正規表現ではマッチングされません。

lookaround は正規表現でマッチさせることができる言語にも影響するのでしょうか。つまり、他の方法ではマッチしないのに、lookaround を使用してマッチすることができる言語はありますか? もしそうなら、これはすべての種類の lookaround (否定的または肯定的な lookahead または lookbehind) に当てはまるのでしょうか、それともそのうちのいくつかに当てはまるのでしょうか?

どのように解決するのですか?

他の回答が主張するように、ルックアラウンドは正規表現に余分な力を加えるものではありません。

次のようなものを使ってこれを示すことができると思います。

ワンペブル2-NFA (を参照しています（参照した論文の「はじめに」の項を参照）。

1ペブル2NFAはネストしたルックヘッドを扱わないが、マルチペブル2NFAの変種を使うことができる（以下のセクション参照）。

はじめに

2-NFAは非決定論的有限オートマトンであり、入力に対して左右どちらかに動く能力を持つ。

1ペブルマシンとは、マシンが入力テープ上にペブルを置くことができ（つまり、特定の入力シンボルにペブルをマークする）、現在の入力位置にペブルがあるかどうかに基づいて、おそらく異なる遷移を実行することができるものです。

One Pebble 2-NFAは通常のDFAと同じ力を持つことが知られています。

非ネスト型ルックアヘッド

基本的な考え方は以下の通りです。

2NFAは、入力テープを前進または後退させることにより、バックトラック（または「フロントトラック」）を可能にします。つまり、先読みのために、先読みの正規表現にマッチし、その後、先読みの正規表現にマッチして、消費したものをバックトラックすることができるのです。バックトラックを止めるタイミングを正確に知るために、ペブルを使う。ルックヘッド用の dfa を入力する前にペブルを落とし、バックトラックを停止する必要がある場所をマークします。

このように、ペブル2NFAを通して文字列を実行した最後に、ルックヘッド式にマッチしたかどうかがわかり、残された入力（すなわち、消費されるために残されたもの）は、まさに残りのものにマッチするために必要なものなのです。

つまり、u(?=v)w という形のルックアヘッドに対して

u、v、wのDFAがあります。

uのDFAのaccepting状態（そう、1つしかないと考えてよい）から、vのstart状態へe遷移し、入力にペブルマークをつけます。

vの受理状態から、小石を見つけるまで入力を左に動かし続ける状態にe遷移し、その後wの開始状態に遷移します。

vの拒否状態から、小石を見つけるまで左に移動し続ける状態に電子遷移し、uの受け入れ状態（すなわち、私たちが去った場所）に遷移する。

r1 | r2、またはr*などを示すために通常のNFAで使用される証明は、これらの1つのペブルの2nfasのために引き継がれます。以下を参照してください。 http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsa を参照してください。また、r*式などでは、構成するマシンがどのように組み合わされ、より大きなマシンを生成するかについての詳細な情報も参照してください。

上記のr*などの証明がうまくいくのは、繰り返しのためのコンポーネントnfasを入力するときに、バックトラックによって入力ポインタが常に正しい場所にあることが保証されているからです。また、ペブルが使用中であれば、それはルックアヘッドコンポーネントマシンの1つによって処理されていることになる。ルックヘッドマシンからルックヘッドマシンへの遷移は、完全にバックトラックしてペブルを取り戻すことなく行われるため、1 つのペブルマシンがあればよいのです。

例えば、([^a] | a(?=...b))* を考えてみましょう。

という文字列とabbbという文字列があるとします。

a(?=...b) のpeb2nfaを経て、最後に (bbb, matched) という状態になります（つまり、入力bbbが残っていて、「a」の後に「...b」がマッチしている状態です）。ここで、*があるので、最初に戻り(上のリンクの構成を参照)、[^a]のdfaを入力する。bにマッチしたら、最初に戻って、もう一度[^a]を2回入力し、acceptする。

ネストしたLookaheadsの処理

ネストしたルックヘッドを扱うには、ここで定義されたk-pebble 2NFAの制限されたバージョンを使用することができます。 2ウェイ・マルチペブルオートマトンおよびその論理の複雑さの結果 (定義4.1および定理4.2参照)。

一般に、2ペブルオートマトンは非正規集合を受け入れることができるが、以下の制限により、kペブルオートマトンは正規であることを示すことができる（上記論文の定理4.2）。

ペブルをP_1, P_2, ..., P_K としたとき

• P_{i+1}はP_iが既にテープ上にない限り置くことができず、P_{i}はP_{i+1}がテープ上にない限り拾うことができない。基本的に小石はLIFO方式で使用される必要があります。

• P_{i+1}が配置されてから、P_{i}が拾われるかP_{i+2}が配置されるまでの間、オートマトンはP_{i}の現在の位置とP_{i+1}の方向にある入力語の終わりの間にあるサブワードのみをトラバースすることが可能である。さらに、このサブワードでは、オートマトンはペブルP_{i+1}を持つ1-ペブルオートマトンとしてのみ動作することができる。特に、別のペブルを持ち上げたり、置いたり、あるいはその存在を感じたりすることは許されない。

つまり、vが深さkのネストされたルックアヘッド式であれば、(?=v)は深さk+1のネストされたルックアヘッド式である。内のルックアヘッドマシンに入るとき、これまでにいくつの小石を置かなければならないかを正確に知っているので、どの小石を置くかを正確に決定でき、そのマシンを出るとき、どの小石を持ち上げるかを知っています。 深さtのすべてのマシンは、ペブルtを置くことによって入り、ペブルtを取り除くことによって出る(つまり、深さt-1のマシンの処理に戻る)。完全なマシンの実行は、木の再帰的dfs呼び出しに見え、マルチペブルマシンの上記の2つの制限に対処することができる。

ここで、式を組み合わせるとき、rr1については、連結するので、r1のペブル番号はrの深さだけ増分されなければなりません。

したがって、ルックヘッドを持つ任意の式は、ペブルの配置に上記の制限を持つ等価なマルチペブルマシンに変換することができ、したがって正規である。

結論

これは基本的にフランシスのオリジナルの証明における欠点に対処するものです。つまり、将来のマッチに必要なものを消費するルックヘッド式を防ぐことができます。

Lookbehindsは単なる有限の文字列であるため（実際には正規表現ではありません）、最初にそれらを処理し、次にlookaheadsを処理することが可能です。

不完全な文章で申し訳ありませんが、完全な証明には多くの図形を描く必要があります。

私には正しく見えますが、間違いがあれば（私は好きなようです :-)）教えていただけると幸いです。