読者です 読者をやめる 読者になる 読者になる

yamaguchi.txt

開発日記。備忘録代わりだよ。

計算困難さ、NP完全とは?

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

形式言語とオートマトン、チューリングマシンの関係について

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