咋直观地理解上下文无关语言的泵引理?( 二 )
）。因为我们既然能够对vwx进行套娃，那就说明这个套娃里在某个时间点存在non terminal，而正则语法不允许non terminal右侧有东西。换句话说，uvwxy定理收敛到了
，也就是正则泵引理/uvw定理。
■网友
大概记得，简单说你构造的DFA的一个计算的状态转移序列满足抽屉原理，
应用就是反证法证非正则语言
建议看edX上北大的理论计算机科学概论理论计算机科学基础课程，或者Sipser的《计算理论导引》。
■网友
模糊的印象：泵引理就是一个语言中的一个字符串s在满足“那些条件”的情况下，1 可以被分割成三串字符串xyz（虽然wiki中是五串，但是中间的三串我更想理解成一串非空串(|vx| \u0026gt;= 1)，并且这样子也为了叙述方便）；2 如果xy^nz的长度大于某个长度l，那么xy^(n+1)z和xy^(n-1)z都在这个语言里。泵引理常被用来证明一个字符串**不是**正则语言，方法是选取满足一个语言的字符串xy^nz，推出某一种情况下的xy^iz不是在这个语言中的，违反了泵引理，因此这个语言不是正则语言。如果i\u0026lt;n，叫做“抽取”（从字符串中抽出一些字符串）；如果i\u0026gt;n，叫做“泵入”。也就是说这个东西是个双向的工具。觉得像一种归纳法。因为书不在身边难免有所疏漏，建议参考Sipser的《计算理论导引》。貌似除了证明“不是”以外（被我叫做“泵出bug了”），基本上没什么用途。就是个除虫工具。
推荐阅读
- 学图像处理有哪些不错的书推荐
- 应该怎样理解会员服务的法律性质
- 读书读到3分之一的时候感觉很难理解，要不要继续
- 怎样简洁到位地让外国人理解中文互联网文化中的「屌丝」、「喷子」、「五毛」、「水军」、「公知」等词
- ActiveMQ、MQTT的方式进行Android消息推送，我的理解是否正确
- 讲座|启东系统培训帮助老师和家长更好理解孩子
- 设计师应该咋快速理解程序，我很想学好程序，但没咋理解程序是咋实现的，大部分教程都是教写的过程
- 复习|七年级英语期末阅读理解专项复习5篇及答案解析
- 图像的傅里叶变换的理解问题
- 白夜追凶2|《白夜追凶》或没有第二部，导演透露不打算再拍了，网友：理解