正規表現であるStringの集合を定義する

質問

次の特徴を持つStringの集合を定義する正規表現Ｑはどのように表せばいいでしょうか？

１．0と1のみを使うString
２．「接頭辞」の0の数が1の数より２つ多くない
３．「接頭辞」の1の数が0の数より２つ多くない

接頭辞とはあるStringの先頭から始まる全てのsubstringのことです。例として123456789の接頭辞は"", 1, 12, 123, 1234, 12345, ..., 123456789となります。

この正規表現Ｑによって定義されるStringの集合の例として
"", 10, 01, 0101, 1010, ...

正規表現Ｑで定義できない集合の例は
0011, 1100, 1110100, 10101100, ...
0011には接頭辞00が存在し、これは0の数が1の数より２つ多いので（0の数は２で1の数は０）正規表現Ｑでは定義できません。

これは不可能でしょうか？不可能の場合文脈自由文法で定義は可能でしょうか？

回答No.1

Tacosan · ベストアンサー

これくらいなら正規表現で書ける.
まず, 文字列のそれぞれの位置に対して「それまでの 0 の個数と 1 の個数の差」に着目する. すると, この差は偶数番目の位置なら偶数, 奇数番目の位置なら奇数になる. つまり, 文字列の 2番目の位置に対しては -2, 0, 2 の 3通りの可能性があるが, 条件から 0 以外は不適. ということは, 「先頭の 2文字」の中には 0 と 1 がそれぞれ 1つずつ存在しなければならない. もちろん, このようなパターンは 2通りあってそのどちらでもよい.
ということで, 文字列の長さが偶数のときにはそのようなパターンが並んでいるということになる. 一方長さが奇数のときには最後に 1文字残ってしまうが, ちょっと考えればわかるようにこの最後の文字は 0 でも 1 でもかまわない.
ここまでくれば正規表現Q は得られるはず. あえて答えは書かないが頑張れ.
でも, なんか言葉遣いが怪しいなぁ. 「正規表現Ｑによって定義されるStringの集合の例」とか「正規表現Ｑで定義できない集合の例」というのは表現として間違っているんだけど気づいてる?

お礼

分かりやすい説明ありがとうございます。すぐに分かりました。
表現が間違っていてすみません。以後気をつけます。