オートマトンと計算理論メモ用

一般に、チューリング機械のように、「次の動作」が「現在読んでいる記号」と「内部状態」に依存して決定される計算モデルをオートマトンと呼ぶ。

第１章
文章の正しさを解析する。
条件：（　と　）の数が同じ。
解答例：スタックを使用して、（　ならAを入れて、）ならAをとる。

形式言語の導入
文字：日本語：ひらがな、カタカナ、漢字
　　　形式言語：０，１、a,b,c

 空列:=長さが０の列

逆x

空集合：ど