context-free-grammar - ポンピング補題を使用して、文法が文脈自由でないことを証明しますか?

Question

ポンピング補題を使用してコンテキストフリーではないことを証明しようとしてL={y#x|(y is a substring of x) ∧x,y∈{a,b}^* }いますが、それができないようです。もしも

|vy|≠ε ,|vxy|≤k , uv^n xy^n z∈L ,∀n≥0

次に、とのvxy両方、または のみまたは のみのいずれかです。abba

それを示すためにどのようにポンピングできますか？

Answer 1

私は cHao に同意します。ポンピング補題を使用して、言語がコンテキスト フリーではないことを示します。言語が文脈自由であることを証明するには、文脈自由文法または DFA を構築します。

{y#x | yxアルファベット上の } のサブセットは、{a, b}*ちょっと見ただけでは文脈自由ではないようです。

s = (a|b)^p#(a|b)^(2p)これは、これを簡単なサブセットにするために、文字が前後にある文字p列です。#2p

この文字列をとx y^i zの部分に分解する必要が|y| > 0あり|xy| = pます。したがって、yは、 の前に任意の文字列で作成する必要があります#。#この文字列を最初の文字列よりも大きくする前に、この文字列を「汲み上げる」ことができます。これは、後半のサブセットではなくなりました。これは矛盾しているため、この言語は文脈自由ではありません。