時間オーバーしちゃった

学生に解答させるとなかなか、出てこなくて…。いや、その時間も見越して時間をとるべきなんですが、説明が少し長かったです。うーにゅ、反省。長かったからといって理解はしていないの罠。ワナワナ。

DFAの最小化アルゴリズムも慣れると楽しいのですが。終わりのミニテストだけ出てきても理解できないよ、学生さん。TDDのように、こまめにステップステップ確認できればいいんだけどね。

最小化アルゴリズムステップ0のチェック

マトリックスを作りなさい。
→マトリックスが間違いなく作れるまで数例がんばらせる。

最小化アルゴリズムステップ1のチェック

空列εで区別可能な組み合わせ、つまり、最終状態とそれ以外の組のマトリックスにXをつけなさい。
→最終状態同士はつけちゃだめというのは間違いやすい。のでこれもバリエーションつけて。

最小化アルゴリズムステップ2のチェック

Xのついてない組について、区別可能か判定をかける。つまりその組の0,1(もしくはアルファベットΣの要素すべて)の遷移先が区別可能かしらみつぶしに調べる。
→ひたすらしらみつぶし。ともに最終状態かループにはまったとき終了ということに気づく例を選ぶ。

これぐらい練習させれば脳内回路のテストになるだろうか。ここまですると時間内には終わらないので毎回宿題を出すべきということに。そうすると、とても採点がやってられないので、コンピュータあたりで問題生成およびチェックできるようにできないかな。いやその仕組みを組む方が大変では＞自分。うーむ。

あと、落とし穴系があるんだよね。DEAD STATEが省略されてしまっているDFA(それはDFAと違うだろ…なんだけど省略形として許容されている)は、そのままやると最小化アルゴリズムの結果が変になるよ、とか。初期状態からパスのない状態は実は最初から省いていいんだよ、とか。