反復補題の不十分性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/10/01 03:04 UTC 版)
「正規言語の反復補題」の記事における「反復補題の不十分性」の解説
反復補題は、ある言語が正規言語であるための十分条件ではないことに注意されたい。つまり、正規言語以外でもこの反復補題が成り立つことがある。言語 L について反復補題が成り立たない場合、L が正規言語でないことがわかる。しかし、反復補題が成り立ったとしても、L が必ず正規言語であるとは言えない。例えば、言語 {uuRv : u,v ∈ {\displaystyle \in } {0,1}+}（アルファベット {0,1} で構成される回文形式の空でない文字列に別の文字列が付属したもの）は正規言語ではないが、p = 4（w=uuRv の長さが 4 以上の場合）で反復可能である。u の長さが 1 であれば、|v| ≥ 2 であり、v の先頭の文字を y とすればよい。さもなくば、u の先頭文字を y とする（k ≥ 2 のときの yk は空でない回文 yy で始まる文字列を構成し、残りを v と見なせば、この言語に属することになる）。正規言語のより実用的な判定方法についてはマイヒル-ネローデの定理を参照されたい。ある言語が正規言語であることを証明する典型的な方法は、その言語を受理する有限オートマトンか正規表現を構築することである。
※この「反復補題の不十分性」の解説は、「正規言語の反復補題」の解説の一部です。
「反復補題の不十分性」を含む「正規言語の反復補題」の記事については、「正規言語の反復補題」の概要を参照ください。
ウィキペディア小見出し辞書の「反復補題の不十分性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 反復補題の不十分性のページへのリンク
