问题：给定语言中的字符串 x ，如何在语言中获得更长的字符串？答：我们可以在 x 的正面和背面添加具有相同数量 a 的字符串 .
这些是足够的提示开始 . 我们可以从一个粗略的想法开始：
S := C | ASA
C := c | cC
现在，诀窍是找出A的制作，它将为我们提供语言中的所有字符串，但只给我们语言中的字符串 . 假设A的产生可以产生具有不同数量的 a s的字符串;这会打破我们的语法，因为你可以把更少的 a 放在前面而不是后面，得到一个不在语言中的字符串 . 这意味着无论我们为A添加什么产品，我们都应该只获得包含一些固定数量 a 的字符串 . 另外，我们想要选择多个 a s，这样，通过将它们放在一个线性组合中，我们可以在最后的字符串中得到 a 的所有数字，即通过附加许多As，我们应该能得到任何数字 a s . 说服自己，A的产品生成的 a 数量的单个值的唯一逻辑选择是一（1） . 这表明 A := XaY ，其中 X 和 Y 不会产生 a .
我们还必须允许任何位置的任意数量的 b 在我们的字符串中 . 这部分实际上很简单 - 我们可以使用 B = (empty) | bB 来获取任意数量的 b . 由于 A 只产生一个 a ，我们可以将 A := BaB 作为我们的产品，以便 A 生成 b*ab* . 我们的语法现在是：
S := C | ASA
A := BaB
B := (empty) | bB
C := c | cC
它接受的语言如下： (b*ab*)^n c+ (b*ab*)^n for any nonnegative n . 这里， n 是在派生字符串时应用规则 S := ASA 的次数 .
1 回答
所以我们需要
uxv，u和v是a和b的字符串，x是c的字符串，u和v具有相同数量的a？当你试图找出某种语言的语法时，有必要考虑一些你可以想象在语言中的最短词，以及你可以用什么规则来制作更大的词 . 这些最短的字符串和规则将成为你语法的产物 .
问题：这种语言中最短的字符串是什么？答案：
c.问题：给定语言中的字符串
x，如何在语言中获得更长的字符串？答：我们可以在x的正面和背面添加具有相同数量a的字符串 .这些是足够的提示开始 . 我们可以从一个粗略的想法开始：
现在，诀窍是找出A的制作，它将为我们提供语言中的所有字符串，但只给我们语言中的字符串 . 假设A的产生可以产生具有不同数量的
as的字符串;这会打破我们的语法，因为你可以把更少的a放在前面而不是后面，得到一个不在语言中的字符串 . 这意味着无论我们为A添加什么产品，我们都应该只获得包含一些固定数量a的字符串 . 另外，我们想要选择多个as，这样，通过将它们放在一个线性组合中，我们可以在最后的字符串中得到a的所有数字，即通过附加许多As，我们应该能得到任何数字as . 说服自己，A的产品生成的a数量的单个值的唯一逻辑选择是一（1） . 这表明A := XaY，其中X和Y不会产生a.我们还必须允许任何位置的任意数量的
b在我们的字符串中 . 这部分实际上很简单 - 我们可以使用B = (empty) | bB来获取任意数量的b. 由于A只产生一个a，我们可以将A := BaB作为我们的产品，以便A生成b*ab*. 我们的语法现在是：它接受的语言如下：
(b*ab*)^n c+ (b*ab*)^nfor any nonnegativen. 这里，n是在派生字符串时应用规则S := ASA的次数 .