翻訳と辞書 Words near each other ・ 正規直交基底 ・ 正規直交系 ・ 正規社員の解雇条件緩和論 ・ 正規社員の解雇規制緩和論 ・ 正規空母 ・ 正規空間 ・ 正規職員 ・ 正規行列 ・ 正規表現 ・ 正規言語 ・ 正規言語の反復補題 ・ 正規軍 ・ 正規部分群 ・ 正規閉包 ・ 正規雇用 ・ 正規順序積 ・ 正視 ・ 正視眼 ・ 正覚 ・ 正覚坊 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 正規言語の反復補題 ： ミニ英和和英辞書 正規言語の反復補題[せいきげんごのはんぷくほだい] ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 正 ： [ただし, せい, しょう] 　【名詞】 1. (logical) true　2. regular　 ・ 正規 ： [せいき] 　 1. (adj-na,n,adj-no) regular　2. legal　3. formal　4. established　5. legitimate　 ・ 言 ： [げん] 　【名詞】 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　 正規言語の反復補題 ： ウィキペディア日本語版 正規言語の反復補題[せいきげんごのはんぷくほだい] 正規言語の反復補題（英: Pumping lemma for regular languages）とは、全ての正規言語が持つ属性を与える補題である。反復補題一般の具体例の一つである。その主たる用法は、ある言語が正規言語でないことを証明することである。 この反復補題は1961年に Y. Bar-Hillel、M. Perles、E. Shamir によって最初に示された〔Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", ''Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung'' 14 (1961) pp. 143-172. 〕。 == 形式的定義 == $L$ を正規言語とすると、$L$ のみに依存する次のような反復長 $p\backslash geq\; 1$ が存在する。$L$ に属する長さ $p$ 以上の任意の文字列 $w$ は $w=xyz$ と書ける（つまり、 $w$ は3つの部分文字列に分けられる）。ここで、 $x$、$y$、$z$ は次の条件を満たす。 # $|y|\backslash geq\; 1$ # $|xy|\backslash leq\; p$ # 全ての $i\backslash geq\; 0$ について、$xy^iz\; \backslash in\; L$ ''y'' は反復される部分文字列（0回を含む任意の回数繰り返され、結果として生成される文字列も ''L'' に属する）。|''y''| は文字列 ''y'' の長さを意味し、(1)の条件は ''y'' が少なくとも長さを持つ空でない文字列であることを意味している。(2)の条件は繰り返しが先頭から ''p'' 文字以内から開始されることを意味する。''x'' および ''z'' については特に制限はない。 反復補題の形式的表現を以下に示す。 $$ \begin (\forall L\subseteq \Sigma^ *) \\ \quad (\mbox(L) \Rightarrow \\ \quad ((\exists p\geq 1) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\ \quad ((\exists x,y,z \in \Sigma^ *) (w=xyz \land (|y|\geq 1 \land |xy|\leq p \land (\forall i\geq 0)(xy^iz\in L)))))))) \end 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「正規言語の反復補題」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.