Re: [請益] 一個關於句法的問題
※ 引述《HotDesert (熱啊!)》之銘言：
: 為什麼可以證明英文不是finit state啊？簡單來說, 英文裏既然有一種
: 句形不是finite state, 整個語言自然也不是finite state啊! 這個推論
: 應該還好吧!
這個推論不好，因為有很多語言本身是 finite state 但包含非 finite state
的子集。例如 a^n b^m 包含 a^n b^n.
實際上證明英文非 finite state 的推論如下：用反證法。假設英文是
finite state。令 S 為以下這個 finite state 語言：
The (girl|boy|cow) (that the (girl|boy|cow))* (chased|kissed|blushed)*
由語感實驗推知，英語與 S 的交集是一個可以用 pumping lemma 證明非
finite state 的語言。但是數學已證任何兩個 finite state 語言的交集均為
finite state。故得矛盾。
--
▼ 單中杰．ccshan@post.harvard.edu．善終結 ▼
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.15.246.94
※ 編輯: ccshan 來自: 76.15.246.94 (07/19 19:53)
推
07/19 21:38, , 1F
07/19 21:38, 1F
推
07/20 01:00, , 2F
07/20 01:00, 2F
推
07/21 03:27, , 3F
07/21 03:27, 3F
討論串 (同標題文章)