type 1 grammer是什么意思,

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/07 18:35:28

type 1 grammer是什么意思,
type 1 grammer是什么意思,

type 1 grammer是什么意思,
1型文法的意思
1型文法
1型文法也叫上下文有关文法,此文法对应于线性有界自动机.它是在0型文法的基础上每一个α→β,都有|β|>=|α|.这里的|β|表示的是β的长度.
注意:虽然要求|β|>=|α|,但有一特例:α→ε也满足1型文法.
如有A->Ba则|β|=2,|α|=1符合1型文法要求.反之,如aA->a,则不符合1型文法.