次のCFLと非CFL CFLの統合はそれですか？

Question

私はTAであり、学生から次の質問を受けました。恥ずかしいことに、私は答えを出すことができなかったので、私はあなたに回っています。

私はL_1 = {a^n b^n c^n}は非CFLであることを知っています。 また、L_2 = {a^i b^k c^j：i！= k} がコンテキストフリーであることも知っています。

これらの組合はどうなりますか？ （それは明らかに非正規です） 文脈自由ですか？

Answer 1

私たちは私たちの世界として言語U = {a^i b^j c^k | i、j、kをN}とする。

次に、L_1^C = {a^i b^j c^k | i = jまたはj！= k} = {a^i b^j c^k | i！= j} union {a^i b^j c^k | j！= k} = L_A和集合L_Bである。 L_A = L_2に注目してください。 （L_1^CはL_2^C ^と交差）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ユニオンL_2と表現することができます。我々はすでに、L_2が文脈自由であることを認めている。私たちの宇宙におけるL_Bの補数は、{a^i b^j c^k | j = k}であり、文脈自由である。 2つの文脈自由言語の和集合も文脈自由であるので、はい、L_1共用体L_2は文脈自由です。 L_1ユニオンL_2は、i！= j（aとbの数が異なる）、またはbとcの数が同じであるということと同等であることは明らかです。あなたがそれについて考えるならば、これは言語の要件を完全に把握します。もしi！= jならば、2番目の部分でOKです。私たちがL = 2に収まらない唯一の方法は、私たちがすでにi = jであることを既に知っていれば、j = kを保証することだけを心配することです。

ブール論理では、（aおよびb）または（not a）は（bまたは（aではない）と等価です。言語の

A CFGは以下の通りです：

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

あなたはトップダウンかボトムアップパーサの構造を経由してPDAを得ることができます。