有限状态语法limit status grammar

形式语法的一种分类，通常指“从左到右的语法”。乔姆斯基根据不同的重写规则把形式语法分为四类：(1) O型语法；(2)上下文敏感语法；(3)上下文自由语法；(4)有限状态语法。句子本质上是由概率所决定的一条反应链，每个词既是对前一个词的反应，又是引出下一个词的刺激，语言能力由此可概括为顺序相依的马尔耶夫过程。有限状态语法其重写规则为A→aQ或A→a，其中A和Q是非终极符号。而A→a只不过是A→aQ当Q为空符号时的一种特殊情况。如把A和Q看成不同的状态，那么由重写规则可知，由状态A转入状态Q时，可生成一个终极符号a，故这种语法叫有限状态语法。每一有限状态语法上下文都是自由的，每一个上下文敏感的语法都是O型的，乔姆斯基把O型语法生成的语言叫O型语言，把上下文敏感语法、上下文自由语法、有限状态语法生成的语言分别叫做上下文敏感语言、上下文自由语言、有限状态语言。有限状态语言包含于上下文自由语言中，上下文自由语言包含于上下文敏感语言中，上下文敏感语言包含于O型语言中。虽不能真正揭示语言的产生过程，但形式语法理论是当代计算机科学的基础理论之一，在算法分析、编码技术、图像识别、人工智能等领域中得到广泛应用。