1 自然言語処理論I 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
正規言語の反復補題(英: pumping lemma for regular languages)とは、全ての正規言語が持つ属性を与える補題である。反復補題一般の具体例の一つである。その主たる用法は、ある言語が正規言語でないことを証明することである。 この反復補題は1961年に Y. Bar-Hillel、M. Perles、E. Shamir によって最初に示された[1]。 形式的定義[編集] を正規言語とすると、 のみに依存する次のような反復長 が存在する。 に属する長さ 以上の任意の文字列 は と書ける(つまり、 は3つの部分文字列に分けられる)。ここで、 、、 は次の条件を満たす。 全ての について、 y は反復される部分文字列(0回を含む任意の回数繰り返され、結果として生成される文字列も L に属する)。|y| は文字列 y の長さを意味し、(1)の条件は y が少なくとも長さを
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く