文脈自由言語の反復補題
(Uvwxy定理 から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/06/06 09:16 UTC 版)
文脈自由言語の反復補題(ぶんみゃくじゆうげんごのはんぷくほだい、英: Pumping lemma for context-free languages)は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。
- 1 文脈自由言語の反復補題とは
- 2 文脈自由言語の反復補題の概要
- 3 参考文献
- 文脈自由言語の反復補題のページへのリンク