正規表現であるStringの集合を定義する
次の特徴を持つStringの集合を定義する正規表現Qはどのように表せばいいでしょうか?
1.0と1のみを使うString
2.「接頭辞」の0の数が1の数より2つ多くない
3.「接頭辞」の1の数が0の数より2つ多くない
接頭辞とはあるStringの先頭から始まる全てのsubstringのことです。例として123456789の接頭辞は"", 1, 12, 123, 1234, 12345, ..., 123456789となります。
この正規表現Qによって定義されるStringの集合の例として
"", 10, 01, 0101, 1010, ...
正規表現Qで定義できない集合の例は
0011, 1100, 1110100, 10101100, ...
0011には接頭辞00が存在し、これは0の数が1の数より2つ多いので(0の数は2で1の数は0)正規表現Qでは定義できません。
これは不可能でしょうか?不可能の場合文脈自由文法で定義は可能でしょうか?