空集的无上下文文法？

Question

3

我有一个作业问题，要求生成空集的CFG。我认为应该是以下两种之一，但不确定。

S->S，但这似乎会导致无限循环。

或者

S-> {}，虽然它是“空集”符号，但它既不是变量也不是终端...

- Matt

作业标签已经过时 http://stackoverflow.com/tags/homework/info。尝试将您的作业问题视为一般编程问题，以使其适用于此网站。 - Coral Doe

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andy Hayden · Accepted Answer

写下语法来表示任何有限语言 L 的一种方法是，对于每个在 L 中的 w，在语法中包含 S -> w，即列出所有单词。

例如，语言 L = ['aa'，'ab'，'ba'，'bb'] 由上下文无关文法生成：

S -> 'aa'
S -> 'ab'
S -> 'ba'
S -> 'bb'

当然，通常有更简洁的语法！

在您的示例中，L = [{}]。明确回答您的问题：空集是一个终端，但是用于描述它的值非常取决于您的编程语言（在Python中，您可能会选择set()）。