不規則性を証明する

Question

言語L = {wxwR}とすると、wRはwの逆数であり、xは最小長さ1であり、wは0または1であり、xは1だけで構成される。

この言語が正規ではないことをどのように証明できますか？ポンピング補題を使用する以外の方法はありますか？ポンピング補題を使用している場合は、x、y、zの文字列sを選択する必要があるかどうかをまだ把握していますが、ヒントを教えていただければ幸いです。

ありがとうございます！

Answer 1

ポンピング補題の使い方をもう一度見てください。 x、y、zの各パーティションに対して、ポンプ補助援数条件の1つに違反するような文字列sを選択する必要があります。

したがって、nを「ポンプ音源数」とします。ピックs= 0^n 1 0^nを選択します。 1）あなたは|xy| <= nを知っています。 2）から、あなたは|y|>=1を知っています。従って、yは、0sのみを含む。

以下3）uv^2wもLである必要がありますが、0sの最初のブロックは2番目のブロックよりも長くなります。これは3）が違反しているため、Lが規則的でないことを意味します。