context-free-grammar - 上下文无关语法

Question

我需要帮助理解这个概念。

书中指出

G1:
    A→0A1
    A→B
    B→#

它声明G1生成字符串000#111

并显示一个过程

A → 0A1 → 00A11 → 000A111 → 000B111 → 000#111

我明白这里发生了什么。我不确定的是它是否可以无限循环。

例如：

也可以使用这个过程G1生成0#1

A → 0A1 → 0B1 → 0#1

这本书没有清楚地解释这部分。谢谢

Answer 1

是的，任何产生式都可以应用无数次，从而生成（在这种情况下以及在大多数情况下）无限数量的字符串。^{此文法生成 0 n} #1 ⁿ形式的所有字符串

Answer 2

是的，当然。给定的语法也会生成0#1语言。事情已经很清楚了。如您所见，生成的语言 0#1 是由相同语法生成的前一种语言的子集。