翻訳と辞書
Words near each other
・ 文聖現
・ 文聘
・ 文脈
・ 文脈メニュー
・ 文脈主義
・ 文脈依存文法
・ 文脈依存言語
・ 文脈化
・ 文脈自由文法
・ 文脈自由言語
文脈自由言語の反復補題
・ 文臣
・ 文興
・ 文興進
・ 文花
・ 文花帖
・ 文芸
・ 文芸プロダクションにんじんくらぶ
・ 文芸・書籍サロン板
・ 文芸作品


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

文脈自由言語の反復補題 : ミニ英和和英辞書
文脈自由言語の反復補題[ぶんみゃくじゆうげんごのはんぷくほだい]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [ぶん]
 【名詞】 1. sentence 
文脈 : [ぶんみゃく]
 【名詞】 1. context 
: [みゃく]
 【名詞】 1. pulse 
自由 : [じゆう]
  1. (adj-na,exp,n) freedom 2. liberty 3. as it pleases you 
: [よし]
 【名詞】 1. reason 2. significance 3. cause 
: [げん]
 【名詞】 1. word 2. remark 3. statement 
: [ご]
  1. (n,n-suf) language 2. word 
: [はん, たん]
  1. (n,vs,n-pref) anti- 2. opposite 3. antithesis 4. antagonism 
反復 : [はんぷく]
  1. (n,vs) repetition 2. reverse 
補題 : [ほだい]
 (n) subtitle
: [だい]
  1. (n,vs) title 2. subject 3. theme 4. topic 

文脈自由言語の反復補題 : ウィキペディア日本語版
文脈自由言語の反復補題[ぶんみゃくじゆうげんごのはんぷくほだい]
文脈自由言語の反復補題(ぶんみゃくじゆうげんごのはんぷくほだい、)は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。
文脈自由言語の反復補題は、任意の文脈自由言語でない言語が文脈自由でないことを証明するのに使えるわけではない。場合によってはより汎用化されたオグデンの補題を使う必要がある。
== 形式的定義 ==
言語 ''L'' が有限で文脈自由であるとき、ある正の整数 ''p'' > 0 が存在し、''L'' 内の任意の文字列 ''w'' について |''w''| ≥ ''p'' が成り立つことを以下のように記述する(ここで、''p'' は反復長 (pumping length) である)。
:''w'' = ''uvxyz''
このとき、文字列 ''u''、''v''、''x''、''y''、''z'' について |''vxy''| ≤ ''p''、|''vy''| ≥ 1、そして以下が成り立つ。
: 全ての0以上の整数 ''i'' ≥ 0 について ''uv ixy iz'' が ''L'' に含まれる。
なお、文字列 ''a'' と ''b'' があるとき ''ab'' はその連結した文字列を表し、|''a''| は ''a'' の長さを表す。また、''ai'' は ''a'' を ''i'' 回反復した文字列を表す。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「文脈自由言語の反復補題」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.