Parikhの定理 - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ

この前 Parikh の定理（パリークの定理）を知ってびっくりしたので紹介します。 形式言語界隈では常識らしいです。 三行で説明して 文脈自由言語と正規言語は、単語を記号の度数で同一視（つまり記号の順番を無視する）と、同じクラスになるというものです。 具体的には準線形というクラスになります。 びっくりしませんか？僕はびっくりしました。 基本的な用語の定義 以下、終端記号の集合を とします。 線形部分集合 の元 を用いて と表せる集合のことを線形部分集合(linear subset)といいます。 線形といいつつ だけバイアスがあり なので錐みたいな感じです。 準線形部分集合 線形部分集合の有限族 の和集合 で表される集合のことを準線形部分集合 (semilinear subset)といいます。 語についての Parikh mapping 語 について、 に が登場する回数を とします。このと