context-free-grammar - 空集的上下文无关语法？

Question

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

S->S 但似乎这将是一个无限循环

和

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

Answer 1

为任何有限语言 编写语法的一种方法L是将每个包含w在语法中，即写出所有单词。LS -> w

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

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

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

.

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