语言 L = {a^(n)b^(m)c^(k): m = |i - k|} 的上下文无关文法
Context-free grammar for the language L = {a^(n)b^(m)c^(k): m = |i - k|}
我有这种语言L = {a^n b^m c^k: m = |n - k|}。
我知道 m = |n - k| 可以用两种方式表达
1) m = n - k for n >= k or n = m + k
2) m = k - n for k >= n or k = m + n
因此，我得到两种语言
L1 = {a^n b^m c^k: n = m + k} 和
L2 = {a^n b^m c^k: k = m + n}。
然后我声称 L 是两者的并集，L = L1 U L2.
我不太明白如何生成一个终端的一个指数是其他两个终端的总和的语法。即，在 L1 中你有 n = m + k。
L1 也可以进一步简化为
a^n => a^(m+k) => a^(m)a^(k) 所以 L1 变成
L1 = {a^m a^k b^m c^k: m, k >= 0}
尝试回答
L1 = {a^m a^k b^m c^k: m, k >= 0}
语法 G1
S -> A|B
A -> aAb|lambda
B -> aBc|lambda
对于 L1，您可以使用
S -> aSc
S -> T
T -> aTb
T ->
L2 类似。
a^n b^n:
考虑 CFG：
S ::= aSb | <empty string>
这会生成具有正确匹配指数的所有字符串 a^n b^n。这样做的原因是使用此语法添加 a 还需要添加额外的 b；通过确保每个产品都保留所需的 属性（a 的数量与 b 的数量相同），我们已经确保（通过归纳，因为属性 最初成立，并且每个产品都保留它）它将适用于我们从语法生成的每个句子。
a^n b^m c^(n+m):
如果我们想让语法生成稍微复杂一点的a^n b^m c^(n+m)，我们可以应用类似的推理：我们在语法结构中编码，添加一个a或一个b 需要添加一个 c:
S ::= aSc | T | <empty string>
T ::= bTc | <empty string>
同样，由于每个产品都保留了我们想要的 属性（c 的数量是 a 的数量加上 b 的数量） , 它适用于我们在语法中生成的任何句子。
您可以应用类似的推理来找出将保留您在 OP 中提到的其他数学属性的语法。
我有这种语言L = {a^n b^m c^k: m = |n - k|}。
我知道 m = |n - k| 可以用两种方式表达
1) m = n - k for n >= k or n = m + k
2) m = k - n for k >= n or k = m + n
因此，我得到两种语言
L1 = {a^n b^m c^k: n = m + k} 和
L2 = {a^n b^m c^k: k = m + n}。
然后我声称 L 是两者的并集，L = L1 U L2.
我不太明白如何生成一个终端的一个指数是其他两个终端的总和的语法。即，在 L1 中你有 n = m + k。
L1 也可以进一步简化为
a^n => a^(m+k) => a^(m)a^(k) 所以 L1 变成
L1 = {a^m a^k b^m c^k: m, k >= 0}
尝试回答
L1 = {a^m a^k b^m c^k: m, k >= 0}
语法 G1
S -> A|B
A -> aAb|lambda
B -> aBc|lambda
对于 L1，您可以使用
S -> aSc
S -> T
T -> aTb
T ->
L2 类似。
a^n b^n:
考虑 CFG：
S ::= aSb | <empty string>
这会生成具有正确匹配指数的所有字符串 a^n b^n。这样做的原因是使用此语法添加 a 还需要添加额外的 b；通过确保每个产品都保留所需的 属性（a 的数量与 b 的数量相同），我们已经确保（通过归纳，因为属性 最初成立，并且每个产品都保留它）它将适用于我们从语法生成的每个句子。
a^n b^m c^(n+m):
如果我们想让语法生成稍微复杂一点的a^n b^m c^(n+m)，我们可以应用类似的推理：我们在语法结构中编码，添加一个a或一个b 需要添加一个 c:
S ::= aSc | T | <empty string>
T ::= bTc | <empty string>
同样，由于每个产品都保留了我们想要的 属性（c 的数量是 a 的数量加上 b 的数量） , 它适用于我们在语法中生成的任何句子。
您可以应用类似的推理来找出将保留您在 OP 中提到的其他数学属性的语法。