あんまり分かってなくてテストで破滅しそうなので、勉強すべきところはどこかをまず見ておく(あと一週間後)。 4: チョムスキー標準形 チョムスー標準形の定義を抑える CFGをチョムスキー標準形に直す 非文脈自由文法 CFLに対するパンピングレンマ 定理の理解…

前回はCFLに関してのパンピングレンマだったが、あんまり覚えてない。正則言語だと同じところを2回通って、ループができるか?というところが肝だった(気がする)が、CFLに関してのパンピングレンマだとTreeに関して同じ構造が出てくるか?が肝っぽい、というこ…

今日から第二部。第一部でやったことの一般化になっているらしい。どう一般化になっているかはまだ分からないけど。 生成規則(るーる)を使って考える この方法を使うと正則表現のようなことができそう? 規則はrecursiveに(ちょっと違うか)定義されることもあ…

自分用メモ。ビデオアーカイブを見直しつつ、過去問を見つつ、できるようになっておかないと死亡なトピックをまとめておく。 具体的に解釈された言語 => DFA 具体的に解釈された言語 => 正則言語 NFA => DFA スライドのp51からp63に。p59からが例になってい…

第一部の最後。任意のDFAから、それと等価で状態数が最小のDFAを求める手法。計算機の設計とかで使われるので、重要。 状態数が少ないとハードウェアが小さくできる 情報検索 正則表現のような検索をしたいとき(DFAみたいなものを中で作っているらしい) なん…

この前の続き。 DFAが受理する言語 NFAが受理する言語 正則表現が表す言語 は全て正則言語である、というのを示すのがメインテーマ。正則表現 => NFAの証明。正則表現に現われる演算子の数に関する帰納法で示す。分解していって、一個少ないから帰納法の仮定…

正則言語が 集合和 補集合 共通部分 集合差 連接 閉包 の演算に関して閉じているということを示した。証明自体は簡単。これによりなかなかうれしい性質が得られる。証明のところでは、(NFAではなく)DFAの性質を使っているところがあったりもする。が、前回NF…

朝から衝撃を受ける。決定性有限オートマトンの出力が複数の状態を許したようなものが非決定性有限オートマトンという感じだが、非決定性有限オートマトンも正則言語(決定性有限オートマトンによりacceptされる言語、だったはず)であるらしい。そんでもって…

単位取れるかとかはあんまり気にしてないけど、一番危なさそうと言えばこの授業かも。DFAが受理する語を求めよ的な問題がいくつかあったんだけど、漏れがありまくりでほとんど間違っていた。結構難しいぞ。。。あと、オートマトンの書き方が何通りもあるんだ…