context-free-grammar - 如何使用上下文无关语法提出有限或无限语言的解决方案？

Question

我正在尝试使用上下文无关语法提出有限或无限语言的解决方案。

我有这些语法来确定它是有限语言还是无限语言的解决方案

S -> XY|bb  Step 1
X -> XY|SS  Step 2
Y -> XY|SS  Step 3

所以我会做

S -> XY            From step 1
S -> YYY           From step 2
S -> SSYY          From step 3
S -> SSSSY         From step 3
S -> SSSSSS        From step 3
S -> bbSSSSS       From step 1
S -> bbbbSSS       From step 1
S -> bbbbbbSSS     From step 1
S -> bbbbbbbbSS    From step 1
S -> bbbbbbbbbbS   From step 1
S -> bbbbbbbbbbbb  From step 1

bbbbbbbbbbbb 

所以我在这里知道如何生成这样的单词，但是我如何找到它的有限或无限语言呢？

Answer 1

如果你能证明 S 指向某物和自身，例如：S->bS，那么你的语言是无限的。如果有人试图列出该语言可以表示的所有内容的有限列表，那么您总是可以合法地创建比他有限列表中的任何内容都长一个“b”字符的东西。因此，任何有限列表实际上都不是该语言可以产生的所有内容的完整列表，并且该语言是无限的。