オートマトン

余談

高級言語からMalbolgeに変換するコンパイラを酒井研究室のM2の人が作ったらしい。すげ〜

第5回 正規表現*1

言語上の演算 ペキ演算 これは定義 正規表現として(),+,.(連接),*を利用できる

第4回

ε閉包 状態qからε入力でのみ行ける状態の集合 ε-NFA遷移関数の拡張 ε入力でいけるところはすべて同等の状態みたいな NFAとε-NFAの等価変換 なんか必死で証明してたけど、なんでそんなに苦労するのかすら俺には意味不明だった

第3回

寝た

第2回

DFAの記述方法 A=(Q,Σ,δ,q0,F) Q:状態の有限集合 Σ:有限のアルファベット(入力記号の有限集合) δ:遷移関数 δ:Q×Σ→Q(×は直積) q0:開始状態 F:最終状態・受理状態の集合 遷移表 遷移図 受理 遷移図に以下を満たすパスが存在する 開始状態で始まる 最終状態で…

第1回

オートマトンを学ぶ意味 エレベータの設計ができる!! チューリングマシンの流れ チューリングマシンってコンピュータよりすごいんじゃなかったけ。 より単純な機構 有限オートマトン プッシュダウンオートマトン*1 NP困難な問題にも対応? 1.1.1 有限オート…