context-free-grammar - 上下文无关语法 - 这些是一样的吗？

Question

我只是想知道这些语法是否产生相同的语言。前者是我对作业的回答，后者是教授给出的结果。据我所知，它们产生相同的语言。

Language: L1 = {a^i b^j | i<j and i,j greater or = 0}

我的解决方案：

S::= Ub
U::= Ub | aUb | end

教授回答：

S::= XY
X::= aXb | end
Y::= bY | b

这些语法产生相同的语言吗？

Answer 1

注意：原作者的帖子有错别字，他已经修复了原版。结果，这个答案对编辑后的帖子没有意义。有关此答案评论中的错字和编辑的其他信息。我在下面包含了原始帖子和答案，以防阅读的任何人对这个上下文无关语法问题有类似的问题。

Language: L1 = {a^i b^j | i<j and i,j greater or = 0}

我的解决方案：

S::= aU 
U::= aU | aUb | end

教授回答：

S::= XY
X::= aXb | end
Y::= bY | b

回答：

看来您的答案与教授的答案相反。使用你的，你可以得到字符串 "aaaaa"U::= aU重复使用 then U::= end。使用教授的语法，您无法获得“aaaa”（或任何 a 多于 b 的字符串）。如果您查看教授的语法，您会注意到添加“a”的唯一方法是同时添加“b”。这确保了 a 的数量永远不会多于 b 的数量。您还会注意到，要从 S 中删除 Y，您必须输入“b”。结合这两条规则，我们总是会比 'a' 至少多出一个 'b'，因为我们在最后添加了一个来去掉 Y。

我相信教授的答案在这种情况下是正确的。该i<j条件导致 b 的数量必须多于 a 的条件，这对于教授的语法是正确的，但对于您的语法则不是这样。