• G = (Vn, Vt, S, P)
    • 终极符号, 非终级符号, 一个特殊非终级符号,产生式
  • 类型
    • 短语(0), 对应图灵机(TM)
    • 上下文相关(1), 对应线性有界自动机(LBA)
    • 上下文无关(2), 对应下推自动机(PDA)
    • 线性文法、正则文法、正规文法,对应有限自动机(FA)
      • 无法控制自返数