- 178 名前：名無しさん＠お腹いっぱい。 mailto:sage [03/05/07 17:37]
- まずどのような「状態」があるのかを考える。この場合は
1. aが偶数個、bが偶数個
2. aが偶数個、bが奇数個
3. aが奇数個、bが奇数個
4. aが奇数個、bが偶数個
で初期状態が1でゴールが2となる。
まず最初に1から2に行くには /b/ の1通り。aが来ると4に行く。
4からスタートして1もしくは3を経由し2へ行く最短パターンは /(aa|bb)*(ab|ba)/
以上から /b|a(aa|bb)*(ab|ba)/ が状態2に行き着く最短パターン。←第1段階
次に状態2からスタートして考えると /aa/ で3を経由して2へ戻り、
/bb/ で1を経由して2へ戻り、/ab|ba/ では4へ行ってしまう。
4へ行ってしまった後は先に考えた「2へ行く最短パターン」で帰って来れるので、
2から始まって2に戻るパターンは /aa|bb|(ab|ba)(aa|bb)*(ab|ba)/ となる。
これは0回以上起こり得ることを考慮して第1段階と結合すると
/(b|a(aa|bb)*(ab|ba))(aa|bb|(ab|ba)(aa|bb)*(ab|ba))*/
|
 |
