bb を含まない正規表現

ちょうど２個の b を含まない任意の {a,b} はどう書くのでしょうか？
b が連続する回数は０回、１回、３回、４回、５回、．．．
は良いとします。

b?|bbb+

で b だけの場合は書けるのですが、例えば
abaabbbbaab

などの場合はどうするのでしょうか？

他にも
aaa
a
b
は大丈夫とします。

No.6 回答者： Tacosan 回答日時： 2008/05/15 16:39

あれ? よく問題読んだら「ちょうど 2個の b を含まない」だった. 「bb を含まないもの」だと勘違いしてました. ごめんなさい.

とはいえ難しくはなく,
・高々 1個の b を含む
・3個以上の b を含む
パターンをそれぞれ書いて or で繋げば OK.
「ちょうど 3個の b を含む」パターンは
a*ba*ba*ba*
と書けますから, 3個「以上」だと
a*ba*ba*b(a|b)*
となります. これに前者のパターンを | で結べば OK.

No.5 回答者： notnot 回答日時： 2008/05/15 03:41

他の方も書いてますが、否定は純粋な正規表現だけでは不可能です。

通常は、プログラミング言語の持つ、if-then-elseの機能を使って実現することになります。この問題だと限定された条件なのでPerl拡張などを利用すれば可能な気がしますが、実際にはそこまで頑張らず言語のelseの機能を使うんじゃないかな。

＞範囲が lex と yacc なのですが この場合はどの言語なのでしょう？

lexの正規表現は、egrepの正規表現（伝統的には拡張正規表現と呼ばれますが、多くの言語の扱える正規表現はさらにこれの「拡張」です）に、「開始条件」というlex独自の文脈機能を追加した物なので、おそらく「開始条件」を使うのでしょう。私は詳しくないので、直接の回答は書けませんが。

No.4 回答者： iriyak 回答日時： 2008/05/15 01:23

こんにちは。

> ちょうど２個の b を含まない任意の {a,b} はどう書くのでしょうか？

頭の体操ですね。これは楽しい。

・長さ 0 から 4 まで書き出してみた
・a を 0, b を 1 に置き換えてみた

長さ4までのものを | で並べたらこうなりました。

ε|0|1|00|01|10|000|...|111|0000|...|1111

εを除くと１桁から４桁の２進数のうち２桁の 11 (１０進数の３) を除いたものは受理する、という感じかな??

ε |
(0|1) |
(0|1)0 |
(0|1)(0|1)(0|1) |
(0|1)(0|1)(0|1)(0|1) |
(0|1)(0|1)(0|1)(0|1)(0|1) |
　　　　　:
　　　　　:
　　　　　:

これに + (1回以上) もしくは * (0回以上) で３桁もしくは４桁以降を括ってやればいけそうな予感がします! どんな感じでしょうか??

■長さ0

ε

■長さ1

0
1

■長さ2

00
01
10
11 // 受理しない

■長さ3

000
001

010
011

100
101

110
111

■長さ4

0000
0001

0010
0011

0100
0101

0110
0111

1000
1001

1010
1011

1100
1101

1110
1111

No.3 回答者： Tacosan 回答日時： 2008/05/14 19:51

すみません, 誤解されるとまずいのでちょっと変更:

まず, 与えられた文字列全体を「a だけからなる連」と「b だけからなる連」に分解します. すると, 「a だけの連」と「1個か 3個以上の b だけの連」が繰り返されているということに気付くはずです. つまり, 前者を X, 後者を Y とすると「X と Y が繰り返されている」ということを正規表現で書けばよい, ということになります. これは, 例えば Y?(XY)*X? と書くことができます.
「b が連続しない」というのも同じように考えることができます. 「a だけの連」と「b」が繰り返されているので (X = a+, Y = b として)
Y?(XY)*X? = b?(a+b)*(a+)?
なんですが, (a+)? は a* と等価なのでちょっと最適化したのが #2 です.
あ, 空文字列はいいのかなぁ? ダメなら若干の修正が必要です.

No.2 回答者： Tacosan 回答日時： 2008/05/14 16:40

う～ん, 正規表現は「否定」を苦手にしてるんだよなぁ.... もちろん「ある正規表現を否定した正規表現」を作ることは理論上常に可能なんだけど.

とグチを言ってもしょうがないのでヒント:
「{a, b} 上の文字列で b が連続しない」という正規表現は「b と b の間には a が 1個以上存在する」ということで
b?(a+b)*a*
と書けます.
今の例も, 「『b が 1個か 3個以上ある』というブロックの間には a が 1個以上存在する」と解釈できますね.
とここまで書いておいてアレですが, yacc で作るなら「bb があったら yyerror」とかやった方が早いのかもしれない.

No.1 回答者： sakusaker7 回答日時： 2008/05/14 15:38

とりあえず 'bb' も含めてマッチするので取り込んでから、

'bb' だけ弾くのが楽だしわかりやすいです。

どうしても一つの正規表現で書きたいという話なら、
何の正規表現を使うのか(Perlの拡張を使ってもいいとかダメとか)と
なぜそうしたいのかを補足してください。

この回答へのお礼

回答ありがとうございます。
そうしたい理由は大学の試験でその問題が出たからで、
答えは非公開なので正解はなんだろう、ととても気になるのですが
どうにもアイデアが浮かばないので質問させて頂いてます。

自分は苦し紛れに (a|b?|bbb+)* と書きましたがこれでは
bb になってしまいますよね

範囲が lex と yacc なのですが この場合はどの言語なのでしょう？

お礼日時：2008/05/14 16:21