●S称为非终结符,在推导过程中,可 以被代替的符号。 °(和)称为终结符,在推导过程中,不 可以被代替的符号。 →是产生式系统的元符号,不属于 非终结符,也不属于非终结符
⚫ S称为非终结符，在推导过程中，可 以被代替的符号。 ⚫ (和)称为终结符，在推导过程中，不 可以被代替的符号。 ⚫→ 是产生式系统的元符号，不属于 非终结符，也不属于非终结符
例2-2:由偶数个0组成的串的语言。 自然语言的描述方式: ①00是合法的该语言的基本的串; ②若S是合法的串,则SS是合法的串;
⚫例2-2：由偶数个0组成的串的语言。 ⚫自然语言的描述方式： ①00是合法的该语言的基本的串； ②若S是合法的串,则SS是合法的串；
●形式化的描述方式: ①S00 ②S→ss
⚫形式化的描述方式： ① S→00 ② S→SS
问题: ●将产生式S→SS换成 S→0S0或者S→00s, 是否还产生相同的语言?
问题： ⚫将产生式S→SS换成 S→0S0或者S→00S， 是否还产生相同的语言？
●同一个语言,可以使用不同的产 生式组合来产生。 ●考虑: 由奇数个1组成串的语言的产生
⚫同一个语言，可以使用不同的产 生式组合来产生。 ⚫考虑： 由奇数个1组成串的语言的产生