上下文无关文法的归纳法证明
所以我有这个问题，我正在研究关于上下文无关语法上的归纳证明。
考虑到这个语法
S-> aSb _s_b
使用归纳证明语法生成的字符串没有以abb开头。
很容易看出，这是事实，但我有一些问题，如何作出一个正式的证明。
我在想，要么按照单词的长度按值进行归纳，要么在派生的长度上使用值归纳法(在这种情况下，不知道哪个更好)。
让我们在推导的长度上使用归纳。
基例:推导的长度是一个步骤，那么唯一的可能性是S-> ab，这显然是成立的。
归纳假说:如果S=>w‘有n个导子(n>0)，那么w’不是从abb开始的
归纳步骤：？
归纳步骤是我遇到问题的地方，我不知道该怎么做。
我想知道有人能不能解释一下我应该在那里做什么？
谢谢!
回答 1
Stack Overflow用户
发布于 2014-06-07 17:02:00
对于n上的任何诱导，基例为P(0)或P(1)，诱导假设为P(n)，诱导步骤是证明P(n)隐含P(n+1)。所以你希望你的上岗步骤是：
归纳步骤:假设对于所有w‘，使得S => w’具有n个派生步骤，w‘不是以字符串=>开始，那么证明对于所有w’，使得S‘=>w’用n+1派生步骤，w'‘不是以字符串开始。
换句话说，如果对于长度为n的所有导子，我们都有w不以abb开头的性质，我们希望证明，对于所有长度为n+1的导子，相同的性质仍然成立。
长度n+1的每一个推导都有S -> aSb，s -> SS或s -> ab之一。(如果我们要求n> 0，则最后一个不适用。)所以你想要一个案例分析。
案例1: s -> aSb。如果S可以扩展到单个b，或者是从bb开始的字符串，那么我们已经证明了这个结论。如果我们能证明语言中没有一个词以b开头，或者等价地证明每个单词都以a开头，我们就可以为这种情况建立结论。
病例2: s -> SS。初始字符串abb必须是
- 全部在RHS的第一个S区，或
- 部分在第一个S中，或
- (如果第一个S重写空字符串)在第二个S的开头。
第一种也是最后一种被归纳假说排除在外。那么，有多少种方法可以定义前缀'abb‘之间的第一个S和第二个？我数两个：'a‘+ 'bb’和'ab‘+ 'b’。如果我们能证明这两种语言都是不可能的话，我们就可以自由地回家了。
所以，如果我的任务是提供这个证据，我首先要证明语言中没有一个单词以'b‘开头，然后用它来处理这两种情况。
https://stackoverflow.com/questions/23605846
复制相似问题
腾讯云开发者
