computation-theory - 语言到上下文无关语法

Question

为以下语言提供上下文无关语法。

(a) {a^mb^nc^n | m ≥ 0 and n ≥ 0 }
(b) {a^nb^nc^m | m ≥ 0 and n ≥ 0 }

如果涉及到任何其他规则，例如 m = n 或类似的东西，我可以得到它，但一般 m 大于或等于零？我很困惑。而且我不明白 a 和 b 会有什么不同。这是我从中制作语法的机会：

S1 --> S2 | e
S2 --> aS2bS2c | S3
S3 --> aS3 | S4
S4 --> bS4 | S5
S5 --> cS5 | c

score 1 · Accepted Answer

是a^mb^n m次重复a后面跟着n次重复b吗？看起来您复制粘贴了作业，甚至忽略了将其格式化为在本网站上可读。

假设我没看错，继续……</p>

关键是（在第一语言中）b并且c重复相同的次数。当您匹配 a 时，b您必须同时匹配 a c。匹配此子序列的产生式将是

S1 => e
S1 => b S1 c

请注意，那里有两种语言，因此您需要两个答案。您不会被要求使用一种可以处理两种语言的语法。（在n = m的情况下，主要问题是模棱两可）。

1 回答 1