生成文法/有限状態文法

一定の確率である語が現れたとします。この時、次に現れる語が確率で重みをつけられています。さらに、出現する語は無制限に長い訳ではなく、主語が出たら述語、というように終わりが定義されているものと定義されている、とします。自然言語のこのようなモデルを「有限状態文法 finite state grammar」と言います。

有限状態は、ある状態から次の状態への遷移の連続で表現を産出します。ここで W を語とすると

・・・⌒W_n⌒W_n+1

W₁ の生起が W₂ の生起を決定します。それ故に、ある状態が、いくつかの状態をスキップして別の状態を決定するということはできません。例えば

W₁⌒W₂⌒W₃⌒・・・⌒W_n

W₁ の生起が W₃ の生起を決定したり、W₁ の生起が W_n の生起を決定したりすることはできません。

ノーム・チョムスキーは、有限状態文法が産出できない表現をいくつか指摘しました。