形式言語理論

開講時限・場所

• 金曜 3限 12号館1225教室

担当教員

• 宮野　悟<miya SPAMFREEEEE no AT ims DOT u- DAISAN SHIN tokyo SHI DOT ac DOT jp>

リンク

• http://dnagarden.ims.u-tokyo.ac.jp/miyano/ja/doku.php?id=lectures

休講・補講

• 11/12 休講
• 12/17 休講
• 1/14 休講
• 1/28 補講

教科書・参考書

教科書

• 講義資料

評価基準

課題

過去問解答例

• 2007,2008年の試験問題「問題３」の解答例

• enecreさんが上げてくれた過去問解答を参考に、間違ってると思われたところは訂正。あくまで参考にしてください。

• あきらかに「A4　2枚」制限をぶっちぎってるので注意。
• 2009の(d)は力及ばず。誰かヘルプ。

  • 形式言語理論2009年の3(d)はループを見つければ無限集合、そうでなければ有限な気がする。つまり、有向グラフとみなしたオートマトンを深さ優先探索して探索済み状態ノードに到達すれば無限、そうでなければ有限。自信なし。 -- amylase

  • 「最小オートマトン」の場合はわかりませんが、そうでない場合は例えば落ち込んだら受理状態には至らないようなループがある場合（例えば、記号aのみ受理するオートマトンの初期状態q0からa以外を読んだらq1⇔q2間を行き来するようなループに陥らせるようなものが考えられる）は、「ループがある」⇔「言語が有限集合」とは言えないはず。ただ、状態数を最小に限れば確かにループを発見したら有限ではないと言ってよさそうな気もする。 -- TakuyaKuwahara

  • つまり、「状態数の最小化」の部分は要らなくて、M（M_e）から「終了状態へ到達可能で無い状態を取り除いた」M'を作って、それの中に「ループを見つける」アルゴリズムを適用すればいいって事だよね。終了状態へ到達可能でない状態を取り除くアルゴリズムは命題2.3あたりの応用で、「ループを見つける」は教科書には類例が無いから自分で考える、という感じか。

  • ふつうの深さ優先だとDAGの場合に誤検知しちゃうね。Bellman-Fordをつかうといいと思う。 -- perim

• 訂正：冒頭(a)の「正則言語全体を定義する」は「正則表現全体を定義する」の間違いです。すいません。（3/3 6:15訂正済）
• 訂正２：(b)のアルゴリズムの最終行の「w」は「e」の誤りです。

• 訂正３：(c)の状態数最小化の箇所、「UnMarkedに残っている状態を……」→「UnMarkedに残っている状態のペアを……」ただしこの記述も微妙に危うい。

Category2年冬学期授業