2.上下文无关语法(2型语法)
能力略强于3型正则语法。其形式为:
A→x
其中,A∈N,x∈V
*
,即每条产生是的左侧必须是一个单独的非终结符。在这种形式体系中,规则不依赖于符号A所处的上下文,所以称上下文无关语法。