私は最近、言語が規則的でないことを示すためにポンピング補題を使用するように求められた課題を持っていましたが、残念ながら間違った答えを得ました。
非正規であることを証明する言語は次のとおりです。 L = {a i b j c k : i = j または j = k}
私が与えられたポンピング補題の定義は次のとおりです。
この主題は、私が理解するのが非常に難しいことが証明されており、そのために完全な空気頭のように感じます。そのため、ポンピング補題を適切に適用する方法に関する詳細な説明をいただければ幸いです。
直観的に、ポンピング補題は、通常の言語 L の十分に長い単語 (長さは言語 L のみに依存する) には、必要な回数だけ繰り返すことができるセクション (長さ > 0) が含まれている必要があることを示しています。そのセクションを何度でも繰り返す (元の単語を「ポンピング」する) と、L 言語にもある長い単語が生成されます。
単語の最小の長さは、上記の定義の最初のステップの m です。セクションが繰り返される回数は、上記の定義の 4 番目のステップの i です。
ポンピング補題は通常、言語 L が正則でないことを示すために使用されます。これは矛盾による証明です: L が正則であり、正規言語のポンピング補題が L に対して真であると仮定します。次に、L 内にある十分な長さ * の単語 w を選び、それがどのように分解されても * 一部のポンピングされることを示します。言葉は言語にありません。これは、正しいことがわかっているポンピング補題と矛盾します。したがって、言語が規則的であるという仮定は間違っていたため、言語は規則的ではありません。※の部分は簡単に選べないので、①と③で「相手」が選んでいます。
単語 w は w = xyz と書き直されます。y | > 0 および |xy| <=メートル。x と z の両方が長さ 0 の場合があります。
通常のアプローチは、xy を同じ文字で構成される文字列として選択し、(ポンピング後に) 同じ文字が多くなると L にない単語になるようにすることです。
この投稿では、言語 L の i または k に制限は指定されていないため、i = 0 が許可されていると仮定すると、適切な単語は b^mc^m (つまり、m bs の後に m cs が続く) となる可能性があります。対戦相手がどのような分解を選択しても、y は常にいくつかの bs で構成されます。これらの bs を繰り返すと、cs よりも bs が多く、as がない単語になり、したがって i != j および j!= k となり、その単語は言語に含まれません。