1

L={w|#a(w)=#b(w)=#c(w)}クロージャーを使用して言語が文脈自由ではないことをどのように証明できますか?

ありがとう

編集 :

私はその言語L1 = {a^i b^i c^i | i>=0}が文脈自由言語ではないことを知っています。今、私は別の言語を見つけようとしていますがL2、どこが正規言語L2であるかを矛盾させるために探しています。L1L2L1∩L2

4

1 に答える 1

2

Lからに到達するにL1は、a、b、c に順序を課す必要があります。この順序を強制するために交差できる非常に単純な正規言語がLあります。それが何であるかがわかりますか?

L3 = { w | #0(w) = #1(w) }クロージャー プロパティを使用して非正則であることを証明する方法を知っている場合、この証明は非常に似ています。

于 2012-06-13T02:31:27.330 に答える