【授業】形式言語とオートマトン
連絡　onono@tmu.ac.jp
第一回
チョムスキー階層
教科書買う
直積
{1, 2}, {x,y,z} があったとき{1, x} {1, y} {1, z} {2,x}, {2, y} {2, z}
空列
長さ0の文字列εで表す
文字列の集合を言語という
第二回
https://gyazo.com/9e6286a3a5eeb3d75bb0b3aa19dcfd02
◎は受理
https://gyazo.com/d31568a84c2da162309156ce3b4e757b
https://gyazo.com/b641caca16f6768f27a2e786f850c667
テストでは書き換える問題がでる
受理状態は集合であることに注意
重要そうだけどよくわからん
https://gyazo.com/9d279fc9d20742cfe2da459ddbef185c
第三回
正規言語の集まりは、3つの正規演算に関して閉じている
正規演算...和集合演算、連結演算、スター演算
https://gyazo.com/101412f020b6da6e2d5f419fa658205d
https://gyazo.com/0734650716bbaad4ad4548b48f116c67
第７回
A+...AA*
正規言語(有限オートマトンで表せるやつ)は正規表現(UとかΣとか使うやつ)で変換できる
GNFAを使って作ってく
記憶しておかなければならない言語は基本非正規言語？？
たぶんそれの証明にポンピング補題を使う
#授業