上下文无关文法

我需要帮助理解这个概念。上下文无关文法

书中指出

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

它指出G1生成字符串000#111

，并显示一个过程

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

我知道这里发生了什么英寸我不确定的是它是否可以无限循环。

例如：

可以G1也使用这种方法

A → 0A1 → 0B1 → 0#1

书中并没有解释这一部分作为显然产生0#1。谢谢

2013-03-08 juice

是的，任何生产都可以应用无数次，从而生成（在这个和大多数情况下）无限数量的字符串。此语法生成所有格式的字符串0 ⁿ＃1 ⁿ

2013-03-08 05:12:04 uba

我很感激。它实际上最终在书中说过，但是在他们给出的几个例子后几页。他们正式定义了这个定义。非常感谢。 – juice 2013-03-08 05:36:30

@juice yes你注意到'A→0A1'这里'A'可以用RHS自己生产替换这个规则使它产生无限大的0^n_1^n，'A - > B'被包括来转换感伤形式纳入句子。你可以重写相同的语法，比如'A - > 0A1 | ＃' – 2013-03-08 19:52:17

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

2013-03-08 05:11:32

回答