●→”读作“定义为”或者“是”,它 的左边和右边分别称为该产生式的左 边和右边;
⚫ →”读作“定义为”或者“是” ，它 的左边和右边分别称为该产生式的左 边和右边；
●根据这些规则,也可以生 成任意合法的串;可以判 断一个串是否为合法的串
⚫根据这些规则，也可以生 成任意合法的串；可以判 断一个串是否为合法的串
●产生串的过程为:从S开始,反 复利用产生式的右边代替产生 式的左边(称之为推导过程), 最后,可以得到匹配的()组 成的串
⚫产生串的过程为：从S开始，反 复利用产生式的右边代替产生 式的左边（称之为推导过程）， 最后，可以得到匹配的（）组 成的串
例:串()(()())的产生过程 S=>SS=>(S)S=>(())S =>()(S)=>()(SS) =>())(()S) (()()()) 其中:“=》”表示单步推导过程
例:串(( ))(( )( ))的产生过程 ⚫ S=>SS=>(S)S=>(( ))S =>(( ))(S)=>(( ))(SS) =>(( ))(( )S) => (( ))(( )( )) ⚫其中：“=>”表示单步推导过程
●虽然产生式的个数是有限的, 但是规则是递归的,因而,所 有的小括号匹配的串(有无限 个)均可以由它们产生,它们 组成的集合就称为一个语言
⚫虽然产生式的个数是有限的， 但是规则是递归的，因而，所 有的小括号匹配的串（有无限 个）均可以由它们产生，它们 组成的集合就称为一个语言