読者です 読者をやめる 読者になる 読者になる

形式言語・オートマトン

ポンピング補題の証明問題

反復補題 (pumping lemma) はある言語が正規言語や文脈自由文法でないことを示すときに使う定理である. 正規言語に対する反復補題と文脈自由文法に対する反復補題 *1 は若干異なるから注意すべし. 正規言語のポンピング補題 言語 が正規言語ならば,以下の…