作者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