一般化された「正規言語の反復補題」
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/10/01 03:04 UTC 版)
「正規言語の反復補題」の記事における「一般化された「正規言語の反復補題」」の解説
言語 L が正規言語であるとき、ある数（反復長）p > 0 について |w| ≥ p であるような L の任意の文字列 uwv を以下のように表現できる。 uwv = uxyzv ここで文字列 x、y、z について |xy| ≤ p と |y| > 0 と次が成り立つ。 全ての i ≥ 0 の整数 i について uxyizv が L に属する。 このバージョンでは言語に要求する仕様がより厳密に表されているため、より多くの非正規言語を正規言語でないと証明できる。
※この「一般化された「正規言語の反復補題」」の解説は、「正規言語の反復補題」の解説の一部です。
「一般化された「正規言語の反復補題」」を含む「正規言語の反復補題」の記事については、「正規言語の反復補題」の概要を参照ください。
ウィキペディア小見出し辞書の「一般化された「正規言語の反復補題」」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 一般化された「正規言語の反復補題」のページへのリンク
