-
- いいね！0
IB(カードスリーブが付けられることを想定していない作りをしているボードゲームを呪う者)
@irn_bru_
正直授業の内容をきっちりとTLに載せようとするのは俺には無理なので早く教室にくるんだ！ #形式言語理論追試対策
2015-02-26 13:58:01
IB(カードスリーブが付けられることを想定していない作りをしているボードゲームを呪う者)
@irn_bru_
はい、休憩終わりました けど実況は今まで通り、使い物になんないです #形式言語理論追試対策
2015-02-26 14:02:21
IB(カードスリーブが付けられることを想定していない作りをしているボードゲームを呪う者)
@irn_bru_
ためになる授業なんで実況やめます #形式言語理論追試対策
2015-02-26 14:22:43
IB(カードスリーブが付けられることを想定していない作りをしているボードゲームを呪う者)
@irn_bru_
CFL := { L | L は context-free} reg. CFL. P(Σ*) の関係を書け #形式言語理論追試対策
2015-02-26 14:24:48
IB(カードスリーブが付けられることを想定していない作りをしているボードゲームを呪う者)
@irn_bru_
魔 王 現 る (koba) #形式言語理論追試対策
2015-02-26 14:33:47
koba
@kobae964
CFLに対してChomsky標準形のCFGを考える。その変数の個数をNとすると、高さ(N+1)以上の導出木には必ず同じ変数が上下に登場する。それを利用していくらでも木の高さを高くできる。 #形式言語理論追試対策
2015-02-26 14:48:25
画力・博士号・油田
@bd_gfngfn
#形式言語理論追試対策 の実況を見てると，以前履修できないから講義資料で自習したのに今まるで覚えていないことが多くて，また読み返さないといけない気になってきた
2015-02-26 14:49:48
えびま
@evima0
できる人が実況してると他の人は実況しづらそう(該当者に実況するなと言ってるわけじゃありません、有益だと思います)。 #形式言語理論追試対策
2015-02-26 14:54:14
koba
@kobae964
L1,L2を認識するCFGの規則をつかって、L1∪L2を認識するCFGを構成すればよい。単純に規則を合わせ、L1,L2の開始記号にS1,S2という名前を付け直し、{S→S1, S→S2}という規則を加えればよい。 #形式言語理論追試対策
2015-02-26 14:57:53
koba
@kobae964
「任意のCFL Lに対して、その補集合¬LがCFLである」と仮定して矛盾を導く。 L1∩L2 = ¬(¬L1 ∪ ¬L2)なので、L1∩L2もCFLであるが、これは不合理である。 #形式言語理論追試対策
2015-02-26 15:04:42
koba
@kobae964
オートマトンの受理言語の性質でチェックできるのは基本的には空であるかどうか(emptiness)だけである。 #形式言語理論追試対策
2015-02-26 15:08:35
koba
@kobae964
NFAに対して補集合をとる操作はうまく行かないので、powerset constructionでDFAに変換してからfinal stateであるかないかを切り替える #形式言語理論追試対策
2015-02-26 15:10:21
koba
@kobae964
NFAでもDFAでも辺がループをなすことは十分ありえるが、その場合でもemptiness check(reachablity check)はちゃんと終わる #形式言語理論追試対策
2015-02-26 15:28:21
koba
@kobae964
一般的にグラフの頂点間の到達可能性は幅優先探索でやれば高々頂点数回試せば終わる。nステップ以内に到達可能な頂点集合を帰納的に列挙していき、変わらなくなったら(サチュったら)やめればよい。 #形式言語理論追試対策
2015-02-26 15:31:59
koba
@kobae964
問4は商集合を理解していないときついし、商集合を理解するかMyhill-Nerodeの定理を丸暗記していないとできない #形式言語理論追試対策
2015-02-26 15:34:00