2023年12月11日 - データ構造の朝とオートマトンの夜

sosukesuzuki
·

今日は朝7時くらいに起きてシャワーを浴びて、仕事を始めた。10時には輪講があったから大学に向かった。とは言え自分の担当分じゃなかったから、話を聞きつつ仕事をしていた。

夜は大学でオートマトンと形式言語という授業の勉強をした。文脈自由言語には最左導出が複数あるような曖昧なものがあって、ただ曖昧なものは嫌ですねえという話がある。嫌なので、曖昧さを排除した文脈自由文法みたいなのがあると嬉しい。あるCFGがあるときに、それをNFAに変化して、サブセット構成でDFAに変換して、そいつがDKテストというのをパスすれば、基になったCFGは曖昧ではなく、決定性PDAで表せるものであるらしい。なんとなく、LRパーサーの勉強って今までずっと避けてきたんだけど、こういう勉強をするとLRパーサーを勉強したくなる。