CFG使用的语言是什么？

Question

此CFG描述什么语言？

Answer 1

我们可以用该语言写出一些最短的字符串来获得它的感觉：

S -> aTb -> ab
S -> aTb -> aabb
S -> SS -> … -> abab
S -> SS -> … -> abaabb
S -> SS -> … -> aabbab

我们注意到，语法生成的唯一字符串将S的每个实例都带到ab或aabb。同样，我们只用S就可以得到任意数量的S -> SS中间形式。因此，这是常规语言(ab + aabb)*。

通过对字符串长度n的归纳来证明。

基本情况：最短的字符串ab和aabb在语言(ab + aabb)*中，并且由语法生成，如上所示。

归纳假设：对于长度不超过(ab + aabb)*的所有字符串，语法生成的语言均与k的语言匹配。

归纳步骤：我们必须证明由次高长度的语法生成的字符串是该语言的，而由次高长度的语言生成的字符串是该语法的。注意：语法只能生成偶数长度的字符串，而语言(ab + aabb)*仅包含偶数长度的字符串，因此，实际上，第二高的步骤是大于k的最小偶数。

1. 我们知道语言和语法匹配长度为k的字符串。令X为长度为k的所有字符串的集合，而Y为长度为k-2的所有字符串的集合。然后，该语法通过修改in的字符串的派生生成一组字符串X'。 X额外使用生产S -> SS一次，然后为刚才介绍的S -> aTb -> ab实例选择S。通过修改Y中的字符串派生以额外使用生产S -> SS，然后为刚刚引入的S -> aTb -> aabb实例选择S，该语法还会生成一组字符串Y'。这些相同的字符串与正则表达式匹配，因为X和Y中的字符串匹配，并且X'和Y'只是添加了ab或aabb的那些字符串，Kleene星允许使用。]]]

2. 类似地，与正则表达式匹配的长度为k和k-2的字符串可以在末尾添加ab或aabb（这要归功于Kleene星），以获取所有匹配的长度为k + 2的字符串。但是这些也必须由语法生成，因为前缀是由语法生成的，并且我们有一些产生式（上面概述），可以让我们在派生的字符串中引入额外的ab或aabb。

换句话说，语言是所有字符串的集合，所有字符串都是任意数量的字符串ab和aabb的实例，以任何顺序串联而成。