PDA が同じ長さの 0 と 1 の 2 つのブロックを比較し、後で使用するためにその長さを記憶できる可能性がないため、この言語は文脈自由ではないと思います。
残念ながら、それを証明する方法はわかりません。
ポンピング補題を使ってみましたが無駄でした...
私はまた、言語が文脈自由であると矛盾して仮定し、文脈自由言語と正規言語との共通部分も文脈自由であるという事実を使用しようとしました (神秘的な正規言語 L を見つけることによって)。 ) - 私のすべての努力は無駄でした...
どんな助けでもいただければ幸いです
いいえ、言語 L = { 0 n 1 n 0 k | k!=n } は文脈自由言語ではありません。また、Class of Regular Languages は、クラス Context free languages のサブセットです。
使用するアイデアPDAは、言語が文脈自由ではないことを示すための正しくて明白な方法です。PDAまた、言語 0 n 1 n 0 kを描画することはできません。一致するプレフィックス 0 nから 1 nスタックが空になると、天気サフィックス 0 Kが等しいnかどうかを確認するための情報が格納されていないためです。
ヒント:正式な証明用
L = {0 n 1 n 0 k | k!=n } L の補数は L 'です。
L ' = {{0 n 1 n 0 n } は、よく知られている文脈依存言語です (証明できます)。
そして、文脈依存言語の補語は、それ自体が文脈依存です。
ポンピング補題の場合:
L = {0 n 1 n 0 k | k!=n } は L 1と L 2の結合です。ここで、
L 1 = {0 n 1 n 0 k | k > n } および L 2 = {0 n 1 n 0 k | k < n }、L = L1UL2 _
L 1と L 2 はどちらも非文脈自由言語です。2 つの非文脈自由言語の結合は、非文脈自由です。(文法で簡単に証明できるもの)
また、2 つの状況依存言語の和集合、連結は状況依存です。