連続する0の一対と連続1S

Question

1*(011*)*00(11*0)* 1* intersect 0*(100*)*11(00*1)* 0*

1の連続した0のペアと後半べきですべてのバイナリ文字列と一致する必要が正規表現の最初の半分の一組のバイナリ文字列の正規表現すべてのバイナリ文字列を1組の連続する1にマッチさせます。最初の文字列には1の連続する文字列が含まれ、2番目の文字列には0の連続する文字列が含まれているため、正規表現全体は0個の連続する1個のペアと1個の連続する1個のペア。これは正しいです？

Answer 1

はい、しかしより厳密には、式は正確に1対の0と厳密に1対の1を含むバイナリ文字列と一致します（「最大で」ではなく）。

私はこの方法でそれを証明することができます

ここで私はより簡単であると感じ組合ではなく、交差点を、使用して、これらのセマンティクスをエンコードする別の正規表現です。

(1)?(01)*00(10)*11(01)*(0)?|(0)?(10)*11(01)*00(10)*(1)? 

前半はゼロ一対のもののペアに先行するバイナリ文字列と一致し、後半のものの対がゼロの組に先行するバイナリ文字列と一致します。これらのペアの前後、前後に交互の値が発生することがあります。

文字列は、どちらのパターンにも一致する場合は使用できます（式のように両方ではなく）。

ここで、これらの正規表現のいずれかに基づいて状態遷移を構築することができます。私はあなたのものと次に私のもので、まず下に行った。各番号付き状態には、文字列の残りの部分を記述する正規表現のリスト、および0、1、または行末のいずれかに遭遇したときに発生する状態遷移が含まれます。文字列は、リスト内の正規表現に一致する場合に一致します。

ご覧のとおり、バージョンと私の間の状態遷移は完全に同相です。したがって、これらはまったく同じ文字列を表します。

start (1)?(01)*00(10)*11(01)*(0)? 
     (0)?(10)*11(01)*00(10)*(1)? 
    0 1 
    1 2 
    EOL NO_MATCH 
1  1(01)*00(10)*11(01)*(0)? 
     0(10)*11(01)*(0)? 
     (10)*11(01)*00(10)*(1)? 
    0 3 
    1 2 
    EOL NO_MATCH 
2  (01)*00(10)*11(01)*(0)? 
     0(10)*11(01)*00(10)*(1)? 
     1(01)*00(10)*(1)? 
    0 1 
    1 4 
    EOL NO_MATCH 
3  (10)*11(01)*(0)? 
    0 NO_MATCH 
    1 5 
    EOL NO_MATCH 
4  (01)*00(10)*(1)? 
    0 6 
    1 NO_MATCH 
    EOL NO_MATCH 
5  0(10)*11(01)*(0)? 
     1(01)*(0)? 
    0 3 
    1 7 
    EOL NO_MATCH 
6  1(01)*00(10)*(1)? 
     0(10)*(1)? 
    0 8 
    1 4 
    EOL NO_MATCH 
7  (01)*(0)? 
    0 9 
    1 NO_MATCH 
    EOL MATCH 
8  (10)*(1)? 
    0 NO_MATCH 
    1 10 
    EOL MATCH 
9  1(01)*(0)? 
    END 
    0 NO_MATCH 
    1 7 
    EOL MATCH 
10  0(10)*(1)? 
    END 
    0 8 
    1 NO_MATCH 
    EOL MATCH 

start 1*(011*)*00(11*0)*1* + 0*(100*)*11(00*1)*0* 
    0 1 
    1 2 
    EOL NO_MATCH 
1  11*(011*)*00(11*0)*1* + 0*(100*)*11(00*1)*0* 
     0(11*0)*1* + 0*(100*)*11(00*1)*0* 
    0 3 
    1 2 
    EOL NO_MATCH 
2  1*(011*)*00(11*0)*1* + 00*(100*)*11(00*1)*0* 
     1*(011*)*00(11*0)*1* + 1(00*1)*0* 
    0 1 
    1 4 
    EOL NO_MATCH 
3  (11*0)*1* + 0*(100*)*11(00*1)*0* 
    0 NO_MATCH 
    1 5 
    EOL NO_MATCH 
4  1*(011*)*00(11*0)*1* + (00*1)*0* 
    0 6 
    1 NO_MATCH 
    EOL NO_MATCH 
5  1*0(11*0)*1* + 00*(100*)*11(00*1)*0* 
     (11*0)*1* + 00*(100*)*11(00*1)*0* 
     1*0(11*0)*1* + 1(00*1)*0* 
     (11*0)*1* + 1(00*1)*0* 
    0 3 
    1 7 
    EOL NO_MATCH 
6  11*(011*)*00(11*0)*1* + 0*1(00*1)*0* 
     0(11*0)*1* + 0*1(00*1)*0* 
     11*(011*)*00(11*0)*1* + 0* 
     0(11*0)*1* + 0* 
    0 8 
    1 4 
    EOL NO_MATCH 
7  1*0(11*0)*1* + (00*1)*0* 
     1* + (00*1)*0* 
    0 9 
    1 NO_MATCH 
    EOL MATCH 
8  (11*0)*1* + 0*1(00*1)*0* 
     (11*0)*1* + 0* 
    0 NO_MATCH 
    1 10 
    EOL MATCH 
9  (11*0)*1* + 0*1(00*1)*0* 
     (11*0)*1* + 0* 
    0 NO_MATCH 
    1 7 
    EOL MATCH 
10  1*0(11*0)*1* + (00*1)*0* 
     1* + (00*1)*0* 
     (11*0)*1* + 0* 
    0 8 
    1 NO_MATCH 
    EOL MATCH