nlp1-03.key
1 自然言語処理論Ｉ 3.文法1(文脈自由文法と句構造文法) 2 文脈自由文法(復習) 書き換え規則の集合 A → B C D 左辺は非終端記号1個 右辺は任意の長さの記号列 文法Gは4つ組<VN,VT,P,σ>で定義 3 導出(derivation) 書き換え規則の適用過程を表す 文法 NP → NP and NP NP → n 導出 NP ⇒ NP and NP ⇒ NP and n ⇒ NP and NP and n ⇒ n and NP and n ⇒ n and n and n 4 導出木(derivation tree) 導出を木構造で表現したもの n and n and NP NP NP n NP NP 5 導出木 一つの終端記号列に対し、導出や導出木は 一般に複数存在する and NP n and n NP NP n NP NP n and n and NP NP NP n
正規言語の反復補題 - Wikipedia
正規言語の反復補題（英: pumping lemma for regular languages）とは、全ての正規言語が持つ属性を与える補題である。反復補題一般の具体例の一つである。その主たる用法は、ある言語が正規言語でないことを証明することである。 この反復補題は1961年に Y. Bar-Hillel、M. Perles、E. Shamir によって最初に示された[1]。 を正規言語とすると、 のみに依存する次のような反復長 が存在する。 に属する長さ 以上の任意の文字列 は と書ける（つまり、 は3つの部分文字列に分けられる）。ここで、 、、 は次の条件を満たす。 全ての について、 y は反復される部分文字列（0回を含む任意の回数繰り返され、結果として生成される文字列も L に属する）。|y| は文字列 y の長さを意味し、(1)の条件は y が少なくとも長さを持つ空でない文字列で
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
オートマトンと言語
動的計画法に基づく確率文脈自由文法の変分ベイズ法 栗原 賢一 亀谷 由隆 佐藤 泰介 東京工業大学大学院情報理工学研究科計算工学専攻 確率文脈自由文法の学習法として、I-O アルゴリズ��
http://deepwave.web.fc2.com/automata2.pdf
43 第5章 文脈自由文法 文脈自由言語は，数式などの表現やプログラミング言語での基本的表現構造にかかわっている． 例えば，数式 (x2 + y) ∗ (x + 50)/((y − 690) ∗ (x + y)) の表現構造は次の記
<5461726F2D8EA991528CBE8CEA8F88979D43594B96402E6A7464>
オートマトン・形式言語及び演習
オートマトンと形式言語 反復補題 桔梗宏孝 今日の目標 与えられた言語が正規言語でないことを示す証明 法を学ぶ。 直接議論する方法 反復補題(ポンプの補題)を使う方法 正規言語の復習
