regular-language - 言語の補数 L={a^nb^n | n!=100}

Question

これは客観的な試験問題であり、2 分しか与えられていないため、証明は必要ありません。オプションはregularまたはcflまたはcslです。これに取り組む方法がわかりません。

私たちがそれを次のように書くとしたら

(a^n b^n | n<100) UNION (a^n b^n | n>100)

ここで、最初の部分を L1 と 2 番目の部分を L2 と呼び、次のように補完してみてください。

モルゴンの法則 L'= L1' INTERSECTION L2'

2〜3分しかかからないという事実を考えると、それが正しい方法でも簡単な方法でもないと思います。これに対するより良いアプローチはありますか？

Answer 1

それが正しい方法です。L = {a^nb^n | n<100} UNION {a^nb^n | n>100}

最初の部分は通常で、2 番目の部分は DCFL です。L' = COMP({a^nb^n | n<100}) INTERSECT COMP({a^nb^n | n>100})

正補数は常に正則であり、DCFL 補数は常に DCFL であるため、CFL です。

したがって、通常の交差 CFL は CFL を返します。