complexity-theory - 言語と CFG に関するいくつかの制約

Question

オートマトン理論に関するメモが 1 つあります。

次の言語を検討してください。

L={xy : x,y in {a,b}*}

次の制約を考慮してください。

1) x=y

2) x != y

3) x=(y)逆

4) x の数が y の数と等しくない

制約 2,3,4 は文脈自由である言語を読みました。1から3までのヒントやチュートリアルは大歓迎です。

Answer 1

あなたが言うように、は文脈自由言語ではありません。L1: {xy | x,y ∈ {a,b}* ∧ x=y}

ただし、次のように、非常によく似たものはコンテキストフリーです。L3: {xy | x,y ∈ {a,b}* ∧ x=y-1}

S → Ø
S → a S a
S → b S b

技術的に言えば、質問の他の 2 つの言語は些細なことです。

L2: {xy | x,y ∈ {a,b}* ∧ x≠y}
L4: {xy | x,y ∈ {a,b}* ∧ |x|≠|y|}

制約を満たさない唯一の文字列は空の文字列だからです。空でない文字列は、2 つの等しくない文字列と;Sに自明に分解できます。これら 2 つの文字列の連結が であり、 が空でない限り、2 つの文字列が等しくなく、長さが異なることは明らかです。空でないすべての文字列で構成される言語は、文脈に依存しないだけでなく、規則的でもあります。ØSSS(a|b)+

それはとても簡単だったので、あなたが実際に求めていたものではないのではないかと思いますが、あなたが本当に何を言いたかったのか推測できません. より正確になるように質問を編集することをお勧めします。