4

正規表現のリスト、またはいくつかのドキュメントと調査を並べ替えることができるものを探しています。

それらの特異性/厳格さに応じて

/[a-z]+/           // most strict
/[a-z0-9]+/
/[a-z0-9èòà]+/     // less strict
/.*/

しかし、どうですか

/[a-z]+ABC/
/[a-z0-9]+/

どちらがもう一方よりも具体的ではありませんか？

前もって感謝します

4

3 に答える 3

6

正規表現は、一致する文字列のセット（「正規言語」と呼ばれます）と同一視できます。正規表現に名前が付けられている場合はE、一致する文字列を呼び出しますL(E)。

上記でほのめかしている意味での厳密さは、サブセット関係になります。がの適切なサブセットである場合A、REをREよりも厳密になるように定義します。これにより、「同じ」REの同義語のようなあいまいさが解消されます。これらは、同じ正規言語を使用しているため、まったく同じです。BL(A)L(B)

@yi_Hが指摘しているように、RE言語（いくつかの一般的なアルファベット）のサブセット関係は半順序を形成します。完全な注文が必要なようです。その場合、許容可能な全順序付けは、サブセット関係によって表される半順序付けを埋め込む必要があることを指定できます。

その全順序を構築する方法について明確な答えはありませんが、2つのアプローチが思い浮かびます。

1つ目は、ポンピング補題を利用することです。どのREでも、十分に長い文字列と一致する場合は、サブセクションを繰り返すことにより、最初から構築可能な長い文字列とも一致する必要があります。そのような繰り返しセグメントを持たない最長の一致する文字列の長さを尋ねて、それをメトリックにすることができます。多分それは半順序を尊重（埋め込み）します、多分そうではありません。

もう1つは、REのステートマシンでのグラフ変換を検討することです。AREがREよりも適切に厳密である場合B、状態の折りたたみまたは同様の単​​純化アクションによってB、オートマトンがから計算可能になると思います（ただし、参照はありません） 。Aメトリックを、REの最小のオートマトンの状態の数として定義できます。

于 2011-10-12T22:40:54.480 に答える
3

2番目の例が示すように、正規表現の全順序付けは不可能であり、部分的な順序付けのみが可能です。

さらに悪いことに、同じ正規表現を書く方法はたくさんあります： [ab]bvs (ab|bb)、aa*vs a+。したがって、2つのregexpesが同等であるかどうかを判断することさえ、簡単な作業ではありません。

于 2011-10-12T22:29:30.740 に答える
1

クレイジーなperlのものではなく、純粋な正規表現について話していると仮定すると、受け入れる文字列のセットに基づいて、質問に一致する正規表現の半順序を定義できます（つまり、正規表現を正規言語として表示します） ）。

正規言語の違い、共通部分、および空虚性が決定可能な問題であることを考えると、式の1つが別の式が受け入れるすべての文字列を受け入れるかどうかを通知するアルゴリズムがあることを意味します。

于 2011-10-12T22:48:30.583 に答える