コンパイラに関する質問があります。
{(ab)^n | n >= 0} は正規言語ですか?
しかし、私はその NFA を描くことができます。しかし、ポンピング補題を使用すると、矛盾した答えが得られます。
誰でも私を助けることができますか？
1 に答える
2
このスレッドが古いことは理解していますが、これが同じ状況の別の学生を助けることができる場合に備えて、ここでいくつかの議論があります. この言語は正則であり、ポンピング補題を使用して非正則であることを示すことはできません。
それが規則的であることを確認するには、それを生成するための正規表現またはそれを認識するための NFA を作成するだけで十分です。正規表現は自明です: (ab)*. NFA は簡単です。2 つの状態。初期状態は受け入れますが、その他は受け入れません。a のイニシャルからその他への遷移。a. その他から b のイニシャルへ。終わり。
ポンピング補題がこれに使用できない理由を見てみましょう。ポンピング補題を使用するには、ポンピングする候補部分文字列を選択する必要があります。この言語では、文字列をどれだけ大きくしても、少なくとも 2 の長さの記号の範囲内に次の部分文字列が常に見つかります: ab. これは常に、ポンピング補題が存在すると言うループを構成する部分文字列である可能性があるため、ポンピング補題だけを使用して、その内部のどこかに (ab)* を持つ通常の言語があることを除外する方法はありません。(注: 十分に長い文字列の場合、部分文字列 ba も除外できません)。ポンピングされる部分文字列を選択することはできないため (取得できる場所には制限がありますが、それらは補題であり、あなたが決定するものではありません)、部分文字列のいずれかが機能する場合、
たとえば、L = {a^kb^k | k >= 0} はポンピング レンマを使用して正則ではありません。PL の仮説を満たす限り、どの部分文字列を使用してもかまわない文字列を選択する必要があります。これが、たとえば a^nb^n を取ることが機能する理由です (PL の仮説を満たすすべての部分文字列は a+ の形式であり、b の数を変更せずに a の数を変更するポンピング)。
于 2011-10-21T21:21:44.093 に答える