黑田常态形式

在形式语言理论中，如果所有的生产规则都属于黑田常态形式，那么一个上下文敏感的语法就属于黑田常态形式。

AB→CD或A→BC或A→B或A→a其中A、B、C和D为非终端符号，a为终端符号。有些资料省略了A→B的模式。它是以黑田征之的名字命名的，黑田征之最初称其为线性有界语法–这个术语后来也被其他一些作者使用。

每一个黑田正则形式的语法都是不收缩的，因此，产生了一种语境敏感的语言。反过来说，每一种不产生空字符串的语境敏感语言都可以由黑田法线形式的语法产生。

一个归功于GyörgyRévész的简单技术将黑田形式的语法转换为乔姆斯基的CSG：AB→CD被四个上下文敏感规则AB→AZ，AZ→WZ，WZ→WD和WD→CD取代。

这一技术也证明了每个非收缩语法都是上下文敏感的。对于非限制性语法也有一个类似的正常形式，至少有些作者也称之为黑田正常形式。AB→CD或A→BC或A→a或A→ε其中ε是空字符串。

每个无限制的语法都弱等价于只使用这种形式的产物的语法。如果从上面的规则中去掉AB→CD，那么就可以得到无语境语言。Penttonen正常形式（对于非限制性语法）是一个特例，上面的xxx条规则是AB→AD。

同样，对于上下文敏感的语法，Penttonen正常形式，也称为单边正常形式（按照Penttonen自己的术语）是。AB→AD或A→BC或A→a对于每个上下文敏感的语法，都存在一个弱等价的单边正常形式。

在形式语言理论中，如果所有的生产规则都属于黑田常态形式，那么一个上下文敏感的语法就属于黑田常态形式。AB→CD或A→BC或A→B或A→a其中A、B、C和D为非终端符号，a为终端符号。有些资料省略了A→B的模式。它是以黑田征之的名字命名的，黑田征之最初将其称为线性有界语法–这一术语也被此后的其他一些作者使用。

每一个黑田正则形式的语法都是不收缩的，因此，产生了一种语境敏感的语言。反过来说，每一种不产生空字符串的语境敏感语言都可以由黑田法线形式的语法产生。

一个归功于GyörgyRévész的简单技术将黑田形式的语法转换为乔姆斯基的CSG：AB→CD被四个上下文敏感规则AB→AZ，AZ→WZ，WZ→WD和WD→CD取代。这一技术也证明了每个非收缩语法都是上下文敏感的。

对于非限制性语法也有一个类似的正常形式，至少有些作者也称之为黑田正常形式。AB→CD或A→BC或A→a或A→ε其中ε是空字符串。每个无限制的语法都弱等价于只使用这种形式的产物的语法。

如果从上面的规则中去掉AB→CD，那么就可以得到无语境语言。Penttonen正常形式（对于非限制性语法）是一个特例，上面的第 一条规则是AB→AD。

同样，对于上下文敏感的语法，Penttonen正常形式，也称为单边正常形式（按照Penttonen自己的术语）是。AB→AD或A→BC或A→a对于每个上下文敏感的语法，都存在一个弱等价的单边正常形式。