如何构造生成语言L={a^i b^j c^k | j≠i+k}的上下文无关文法？

首先，你将L拆分为L = L1 ∪ L2的思路完全正确——上下文无关文法对并集的支持非常直接，我们只需要分别构造生成L1 = {a^i b^j c^k | j > i +k}和L2 = {a^i b^j c^k | j < i +k}的文法，再合并即可。

一、构造生成L1的文法（j > i +k） #

L1的核心是b的数量比a和c的总数多，字符串结构为a^i b^{i+k+m} c^k（m≥1），即先生成a^i b^i（每个a对应一个b）、b^k c^k（每个c对应一个b），再插入至少一个额外的b（所有b都在c之前）。

对应的文法规则：

S1 → A1 B C1
A1 → a A1 b | ε   // 生成a^i b^i
B → b B | b        // 生成至少1个额外的b（m≥1）
C1 → b C1 c | ε    // 生成b^k c^k

• 当i=0时，生成b^{m+k} c^k（m≥1），满足j=m+k>k=i+k；
• 当k=0时，生成a^i b^{i+m}（m≥1），满足j=i+m>i=i+k；
• 当i=k=0时，生成b^m（m≥1），满足j=m>0=i+k。

二、构造生成L2的文法（j < i +k） #

L2的核心是b的数量少于a和c的总数，我们可以拆分为三类子情况，分别构造文法：

子情况1：a的数量多于b（i > j） #

字符串结构为a^{m+j} b^j c^k（m≥1），即先生成a^j b^j c^k，再在前面添加至少一个a。

S2a → a S2a | A2 C2
A2 → a A2 b | ε   // 生成a^j b^j
C2 → c C2 | ε     // 生成任意数量的c（k≥0）

子情况2：c的数量多于b（k > j） #

字符串结构为a^i b^j c^{j+n}（n≥1），即先生成a^i b^j c^j，再在后面添加至少一个c。

S2b → S2b c | A3 C3
A3 → a A3 | ε     // 生成任意数量的a（i≥0）
C3 → b C3 c | ε   // 生成b^j c^j

子情况3：a≤j且c≤j，但i+k > j #

这类字符串比如a^2 b^3 c^3（i=2,j=3,k=3），特点是每个a和c都有对应的b，但a+c的总数仍多于b。可以看成先生成a^i b^i，再生成b^m c^k（k > m，m=j-i），保证i+k > i+m = j。

S2c → A2 D
D → b D c | D c | ε  // 生成b^m c^k，其中k > m ≥0

合并L2的规则 #

将三个子情况合并：

S2 → S2a | S2b | S2c

三、合并L1和L2的完整文法 #

将两部分的规则整合，得到生成L的完整文法：

S → S1 | S2

// L1规则
S1 → A1 B C1
A1 → a A1 b | ε
B → b B | b
C1 → b C1 c | ε

// L2规则
S2 → S2a | S2b | S2c
S2a → a S2a | A2 C2
A2 → a A2 b | ε
C2 → c C2 | ε
S2b → S2b c | A3 C3
A3 → a A3 | ε
C3 → b C3 c | ε
S2c → A2 D
D → b D c | D c | ε

验证小技巧 #

可以拿几个典型字符串测试文法是否能生成：

• 对于aabbbcc（i=2,j=3,k=2，j=3 < 2+2=4）：可以通过S2c → A2 D生成，A2生成aabb，D生成bcc（k=2>m=1），合起来就是aabbbcc；
• 对于aaabbbbbbcc（i=3,j=6,k=2，j=6>3+2=5）：通过S1 → A1 B C1生成，A1生成aaabbb，B生成b，C1生成bbcc，合起来就是aaabbbbbbcc。

内容的提问来源于stack exchange，提问作者giraffesyo