14と15のリビジョン間の差分

形式言語理論

開講時限・場所

2007,2008年の試験問題「問題３」の解答例
enecreさんが上げてくれた過去問解答を参考に、間違ってると思われたところは訂正。あくまで参考にしてください。
あきらかに「A4　2枚」制限をぶっちぎってるので注意。
2009の(d)は力及ばず。誰かヘルプ。
- 形式言語理論2009年の3(d)はループを見つければ無限集合、そうでなければ有限な気がする。つまり、有向グラフとみなしたオートマトンを深さ優先探索して探索済み状態ノードに到達すれば無限、そうでなければ有限。自信なし。 -- amylase
訂正：冒頭(a)の「正則言語全体を定義する」は「正則表現全体を定義する」の間違いです。すいません。（3/3 6:15訂正済）
訂正２：(b)のアルゴリズムの最終行の「w」は「e」の誤りです。
訂正３：(c)の状態数最小化の箇所、「UnMarkedに残っている状態を……」→「UnMarkedに残っている状態のペアを……」ただしこの記述も微妙に危うい。

-  ⇤ ← 2011-03-04 03:14:23時点のリビジョン14 → 
  サイズ: 1840
  編集者: amylase
  コメント:
+   ← 2011-03-04 03:17:16時点のリビジョン15 → ⇥
  サイズ: 1843
  編集者: amylase
  コメント:
-削除された箇所はこのように表示されます。
+追加された箇所はこのように表示されます。
 行 25:
-  * 形式言語理論2009年の3(d)はループを見つければ無限集合、そうでなければ有限な気がする。つまり、有向グラフとみなしたオートマトンを幅優先探索して探索済み状態ノードに到達すれば無限、そうでなければ有限。自信なし。 -- [[amylase]]
+  * 形式言語理論2009年の3(d)はループを見つければ無限集合、そうでなければ有限な気がする。つまり、有向グラフとみなしたオートマトンを深さ優先探索して探索済み状態ノードに到達すれば無限、そうでなければ有限。自信なし。 -- [[amylase]]