2

私は TA ですが、学生から次のような質問を受けました。恥ずかしいことに、私は答えを思いつくことができなかったので、皆さんに頼ります。

L_1 = {a^nb^nc^n} が非 CFL であることはわかっています。また、L_2 = {a^ib^kc^j : i != k }は文脈自由であることもわかっています。

それらの結合はどうですか?(明らかに不規則です) 文脈自由ですか?

4

1 に答える 1

3

宇宙として言語 U = {a^ib^jc^k | i、j、k in N}。

L_1^C = {a^ib^jc^k | i!=j または j != k} = {a^ib^jc^k | i!=j} 結合 {a^ib^jc^k | j != k} = L_A ユニオン L_B. L_A = L_2 であることに注意してください。

DeMorgan によると、L_1 結合 L_2 = (L_1^C は L_2^C と交差します)^C = ((L_A 結合 L_B) は L_2^C と交差します)^C、これは分配法則により ((L_A は L_2^C と交差します) 結合 (L_B) L_2^C))^C と交差します。

L_A = L_2 であるため、(L_B と L_2^C が交差)^C が得られることを思い出してください。DeMorgan により、これを L_B^C union L_2 としてレンダリングできます。L_2 が文脈自由であることはすでに認めています。私たちの宇宙における L_B の補数は {a^ib^jc^k | j=k}、これも文脈自由です。2 つの文脈自由言語の和集合も文脈自由なので、そうです、L_1 和集合 L_2 は文脈自由です。

手続きを経て、直観は明らかです: L_1 結合 L_2 は、 i != j (a と b の数が異なる) または b と c の数が同じであると言うのと同じです。考えてみれば、これは言語の要件を完全に捉えています。L_2 に陥らない唯一の方法は、i = j という事実を既に知っている場合であり、j = k を保証することだけを心配する必要があります。

ブール論理では、(a and b) or (not a) は (b or (not a)) と同等です。

この言語の CFG は次のとおりです。

S := A | C
A := aA | B
B := lambda | bBc
C := Cc | D | E
D := a | aD | aDb
E := b | Eb | aEb

トップダウンまたはボトムアップのパーサー構造を介して PDA を取得できます。

于 2012-02-22T15:09:52.417 に答える