我需要帮助理解这个概念。
书上说
G1:
A→0A1
A→B
B→#
它指出G1生成字符串000#111
并显示一个过程
A → 0A1 → 00A11 → 000A111 → 000B111 → 000#111
我明白这里发生了什么。我不确定它是否可以无限循环。
例如:
使用此过程G1也可以生成0#1
A → 0A1 → 0B1 → 0#1
这部分书上没有解释得那么清楚。谢谢
最佳答案
是的，任何产生式都可以应用无限次，从而生成(在这种情况下以及大多数情况下)无限数量的字符串。 此语法生成 0n#1n
形式的所有字符串关于context-free-grammar - 上下文无关语法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15287125/