このブログは備忘録なので、自分が忘れないためにまとめる。 そもそも計算とは。 有限時間内にチューリングマシンで解ける問題。 他の計算可能の定義として、λ計算、再帰関数などがある。しかし、チューリングマシンにも解けない問題が存在し、例えば停止性…

雑です。手書きです。 何かあればコメントしていただきたいです。 全体としてこんなイメージ。 形式言語の文法は、G=&ltN,Σ,P,S>のように表され、Nは非終端記号、Σは終端記号、Pが生成規則、Sが初期記号となっている。正規言語が有限オートマトンと等価であ…