各位pavone、E cup、30cm、勝利組、溫拿、小妹、真強者、高富帥,
大家好!打給厚!胎嘎侯!AV8D!
爆一個語言的文法的卦。所謂「文法」是指像下面這種規則:
句子 = 主詞+動詞+受詞 或 祈使句
祈使句 = 動詞 或 動詞+受詞
主詞 = I 或 You 或 She 或 He 或 They 或 It
動詞 = see 或 eat 或 have
受詞 = me 或 you 或 her 或 him 或 them 或 it
有些文法是"ambiguous"的,ambiguous是指「存在一句合乎文法的話,該句話的結構
可以被以兩種以上方式理解」。請看下面這句話:
if 甲 then
if 乙 then
丙
else
丁
我們有兩種方式理解這句話:
if 甲 then if 甲 then
{ {
if 乙 then if 乙 then
{ 和 {
丙 丙
} }
else }
丁 else
} 丁
也就是「第二個else要跟著哪一個if」的問題!
現在考慮如下的問題:
輸入:任意一個文法,比方說C語言的文法、Java語言的文法等。
輸出:若輸入的文法是ambiguous的,則回答「是」,否則回答「否」。
八卦是:沒有任何程式可以解決上述問題!!!這不是「還沒有人想出來怎麼做」,
而是「已經被證明做不到了」!
※ 引述《Ommm5566 (56天團)》之銘言:
: wiki
: 就廣義而言,是一套的溝通以及符號、表達方式與處理規則,一般稱為文法。符號通常稱
: 為文字會以視覺、聲音或者觸覺方式來進行傳遞。
: 當人發現了某些動物如海豚能夠以某種方式溝通,就誕生了動物語言的概念。20世紀由於
: 計算機誕生,人需要給計算機指令。這種對機器的「單向溝通」就成計算機語言。
: 鄉民的PTT算是哪種語言 有沒有語言的八卦?