证明以下语言是等效的

Question

我需要使用归纳证明以下语言是等效的：

P :: =ε| id | （P）

和

S :: =ε| id | （R

R :: =）| S）

需要证明：

L（P）= L（S）

我该怎么做？

我能够证明L（S）包含L（P），但我不能证明另一个方向。

Answer 1

为了通过归纳产生证据，我们必须陈述声明，在基本情况下表明它是正确的，陈述假设然后表明声明适用于下一个规模的情况。

我们的主张可以是“L（P）和L（S）包含相同的长度为n的字符串，用于所有自然n”。

我们的基本情况可以是两种语言中的几个最小的字符串：L（P）和L（S）都包含空字符串，唯一的零长度字符串;因此权利要求适用于n = 0的情况.L（P）和L（S）都包含id，长度为2的语言中唯一的字符串（假设i和d是不同的符号;如果id是一个符号，那么这些字符串长度为1）。因此，权利要求保持n = 2（或n = 1，取决于）。

我们可以使用强感应而不是简单感应，如下：L（P）和L（S）包含长度最大为k的所有相同的字符串。

现在，我们必须证明，对于下一个最高长度的字符串，一种语言中包含的任何字符串都包含在另一种语言中，反之亦然。

1. 设w是L（P）中下一个更高长度的字符串。由于| w |，用于导出w的第一个生产必须是P :: =（P） > 2（或| w |> 1）我们已经涵盖了较小的案例。然后w =（w'）其中w'是L（P）和| w'|中的字符串<| w |。但是w的长度大于L（P）中的k，所以w'的长度必须小于或等于k。但是，通过归纳假设，w'必须同时在L（P）和L（S）中。因此，推导S :: =（R :: =（S）:: =（w'）有效并产生w。因此，w在L（S）中。
2. 设w是L（S）中下一个更高长度的字符串。用于派生w的第一个生产必须是S :: =（R，下一个生产必须是R :: =）或R :: = S）。让我们分开考虑这些案例。 如果第二个生产是R :: =），则w = S :: =（R :: =（），我们可以验证两种语言（或者我们可以简单地依赖于归纳假设）。 如果第二次产生是R :: = S），则w = S :: =（R :: =（S），所以w的形式为（w'），其中| w'| <| w |。具有大于k的下一个更高的长度，w'具有小于或等于k的长度并且由P的语法生成。