|
以文本方式查看主题 - 计算机科学论坛 (http://bbs.xml.org.cn/index.asp) -- 『 理论计算机科学 』 (http://bbs.xml.org.cn/list.asp?boardid=64) ---- 怎么证明{a^i|i为素数}不是上下文无关语言(CFL)?[求助] (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=57942) |
|
-- 作者：hegonghe -- 发布时间：1/11/2008 3:04:00 PM -- 怎么证明{a^i|i为素数}不是上下文无关语言(CFL)?[求助] 证明:{a^i|i为素数}不是上下文无关语言(CFL)? 怎么证明?谢谢!! |
|
-- 作者：Logician -- 发布时间：1/11/2008 6:16:00 PM -- 反设L={a^i|i为素数}是上下文无关的。 那么，由pumping lemma，存在一个数p，使得对L中任何长度大于等于p的字符串s，s可以被分成5段，s=uvxyz，此分割满足： 1) 对每一个i>=0，u(v^i)x(y^i)z属于L 2) |vy|>0 3) |vxy|<=p 那么任取一个大于p的素数m（由素数的无限性知，这样的m必然是存在的），由pumping lemma，存在k=|vy|>0，使得m+k,m+2k,m+3k,...,m+mk,...都是素数，但是m+mk=m(k+1)，不可能是素数，矛盾。 所以L不是上下文无关的。
|
|
-- 作者：hegonghe -- 发布时间：1/12/2008 11:48:00 AM -- 谢谢 !了 ............ |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
46.875ms |