論理とか文法とかあれこれの表現力のメモ[未整理] regular language < linear language < context free

クリプキフレーム Kripke frame そう言えばクリプキフレームの話を書いていなかった事を思い出したり(クリプキフレームの話なんて素敵なpdf (http://www.is.titech.ac.jp/~kashima/manuscript/03Sept.pdf )がネット上に溢れているので、わざわざ書くようなこ…

2-way 決定性有限オートマトン[2DFA] 直感的な説明をすると, 入力文字列を2方向に走査できるオートマトン。通常のオートマトンでは, キャラクタを受け取るとそのキャラクタと, 現在の状態から次の状態を決定する。その流れは2DFAでも同様に行われるが, 2DFA…