作者ccshan (善終結)
看板Linguistics
標題Re: [請益] 一個關於句法的問題
時間Sun Jul 19 19:51:48 2009
※ 引述《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。故得矛盾。
--
▼ 單中杰．
[email protected]．善終結
▼
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.15.246.94
※ 編輯: ccshan 來自: 76.15.246.94 (07/19 19:53)
1F：推 HotDesert:多謝指教! 看來我也得回去翻翻計算理論的教科書了... 07/19 21:38
2F：推 lingualedwin:原po是超級強者.... 07/20 01:00
3F：推 lovelyaiko:看來~自己還要再多念一點書了^^"~答得好專業 07/21 03:27