オートマトンと形式言語理論

エスケープシーケンスやインジェクション攻撃といった実践的な例とともに、「構造」と「構造を表すための文字列」の違いを意識できるようになる。

再帰的構造を再帰的シリアライザで文字列に「押し込む」という視座を手に入れるとともに、文脈自由文法や JSON に親しむ。

シリアライザから単射性が失われていることの問題点を理解し、上手いシリアライザを設計する必要性について学ぶとともに、実際に用いられているシリアライザでの工夫について具体例を交えて学ぶ。

豊富な例示で有限オートマトン・形式言語・有限オートマトンによる形式言語の識別といった概念に慣れ親しむ。

最小 DFA について学ぶ。NFA と正則表現について学ぶとともに、ε-NFA は正則表現を包摂するのにちょうどいい柔軟さを有した有限オートマトンであることを理解する。

正則表現と有限オートマトンが持つ密接な関係について学び、有限オートマトンにおいて非決定性は識別能力を拡張させないことを学ぶ。

形式言語理論がもたらした極めて実践的な応用例の一つ、regex を導入し、正則表現との類似点や差異を知る。

正則言語が正則表現・DFA・ε-NFA のどれを使っても表せるという強力な事実を利用し、諸性質を示す。

パーサーや BNF といった概念を学ぶとともに、あらゆる文脈自由文法に対して、railroad diagram とも称される「関数呼び出しつきのオートマトン」によるパーサーが実現できることを示す。

中置演算子とカッコを含む数式を再帰下降構文解析で読む。呼び出しスタックの概念に慣れ親しむとともに、後置記法はスタックマシンに対する命令列として解釈できることを学ぶ。

「言語クラスの包含関係を調べるというのは、機械クラスの計算能力の強弱を考えることに他ならない」という観点から学びを整理し、一見距離のある「計算機のモデル」と「形式言語」の 2 つの間の密接な関係を今一度整理する。

連続と離散の狭間を垣間見つつ、自身の記述に用いられているプログラミング言語で書かれた任意のプログラムの停止性を正しく有限時間で判定できるプログラムというのはインターフェースが unreasonable である、という視点から、停止性問題をつぶさに観察する。

P≠NP 予想が如何に重要であり、いかなる意味付けができるのかを理解する。「計算機のモデル」と「形式言語」との間にある関係性をいま一度整理する。

正則表現の言語処理系を実装する。regex と正則表現の違いに今一度立ち返り、regex エンジンを自作することに備える。

自分の手で regex エンジンを実装することで、この授業での幅広い学びを実践的な観点から結びつけるとともに、regex エンジンを「脱・神秘化」(demystify) していくことを目指す。