theory - 通过推导步骤数证明

Question

给定 G = {a, b, c, d}, {S, X, Y}, S, {S->XY, X->aXb, X->ab, Y->cYd, Y->cY, Y ->cd}}

证明 |w|c-|w|d+|w|a≥|w|b

|w|a 是字符串中有多少个 'a。这是有道理的，'c' 将比 'd' 多（或相同数量），因为没有生产规则可以在不制作 ac 的情况下制作广告，而在不使用 Y->cY 的情况下制作 'c'。我需要使用推导步骤数的归纳来正式证明这一点，并且整天都在尝试。任何帮助表示赞赏。

Answer 1

我们将使用这个语法

S -> XY
X -> aXb
X -> ab
Y -> cYd
Y -> cY
Y -> cd

并显示语言的语法有|w|c - |w|d + |w|a ≥ |w|b。X -> aXb证明是通过对产生式Y -> cYd和的应用数的归纳Y -> cY。

基本情况：只有一个字符串在没有调用这些产生式的情况下派生出来，即abcd，并且它满足|w|c - |w|d + |w|a >= |w|b因为1 - 1 + 1 >= 1。

归纳假设：假设该主张适用于使用最多并包括k上面给出的三个产生式之一的应用导出的所有字符串。

归纳步骤：我们证明该声明适用于通过产生式的k+1应用派生的字符串。由于我们的每个产生式在 LHS 和 RHS 中都有相同类型和数量的非终结符，并且由于 RHS 在所有情况下也包含终端，因此在派生的语言中存在一个较短的字符串，这些产生式的应用至少少了一个。根据假设，较短的字符串具有|w|c - |w|d + |w|a >= |w|b. 对于我们的字符串，有三种情况：

1. X -> aXb是k+1应用的st生产。这增加|w|a了|w|b1，我们有|w|c - |w|d + |w|a + 1 >= |w|b + 1iff |w|c - |w|d + |w|a >= |w|b，我们已经确定了。
2. Y -> cYd是k+1应用的st生产。这增加了 1，并且我们|w|c已经确定了iff 。|w|d|w|c + 1 - (|w|d + 1) + |w|a >= |w|b|w|c - |w|d + |w|a >= |w|b
3. Y -> cY是k+1应用的st生产。这增加|w|c了 1，给予|w|c + 1 - |w|d + |w|a >= |w|b这是真的，因为|w|c + 1 - |w|d + |w|a > |w|c - |w|d + |w|a >= |w|b。

在选择k+1st 产生式的三种可能情况的每一种情况下，产生式中派生的字符串都k+1保持该属性。通过归纳，该属性适用于n这些产品的所有应用。