私はそれが規則的でないことを知って{a^i b^j | i = j }おり、ポンピング補題で証明できます。同様に、ポンピング補題を使用して、これも正則でないことを証明できます。しかし、そのような言語が実際には規則的であるという同様の問題があると思います。そして、補題のポンピングに関する知識に自信がないので、この悪い質問をしています。ごめん。
これが私がそれを証明する方法です: w を としましょうa^p b^(19k+p)、明らかにこれは言語にあります。次に、a をポンピングすると、 になりますa^(p+1) b^(19k+p)。失敗します。したがって、定期的ではありません。
私の証明は正しいですか？
この回答を見てください。つまり、文字列を正しくポンピングしていません。ポンピング補題は、文字列がwherewとして分割でき、空ではないことを示しています。次に、すべての i ≥ 0 に対して文字列を xy i zとしてポンプできます。w = xyz|xy| ≥ py
ここで重要なのは、ポンピング補題が、これらの特性を満たす文字列の分割が存在するwこと、分割を選択することはできず、文字列を xy i z としてのみポンピングできることを示していることです。
ただし、この言語は規則的であるため、言語が規則的であるかどうかを証明するためにポンピング補題を使用することはできません。言語が不規則である場合にのみ証明できます (これは必要条件ですが、十分条件ではありません)。言語が規則的であることを示すために、言語を正確に説明する DFA、NFA、または正規表現を作成できます。そのような正規表現の 1 つが次のとおりです。
(a^19)*(e|ab|aabb|aaabbb|...|a^18b^18)(b^19)*
e空の文字列はどこにありますか。
あなたの言語は、オートマトンまたは計算の入門コースの例だと思います。興味のある方は、Myhill-Nerode の定理は入門資料で取り上げられることはあまりありませんが、この場合、規則性を非常に簡単に証明できます。証明はそこから比較的容易に導かれる.