正規数
lim inf n → ∞ C ( S ↾ n ) n < 1 {\displaystyle \liminf _{n\to \infty }{\frac {C(S\upharpoonright n)}{n}}<1}
が成り立つことをいう。ここに、 C ( S ↾ n ) {\displaystyle C(S\upharpoonright n)} はC が S の最初の n 個の文字を読み込んだときに出力した文字の個数を表し、liminf は下極限を意味する。
Ziv, Lempel (1978) は
文字列が正規であることと、その列を「圧縮する」ILFSC が存在しないことは同値である
ことを示した。実際には彼らは次の事実を示している。「ある文字列の ILFSC による最適な圧縮率は、その列のエントロピー率(entropy rate、エントロピーのビット数に対する比)に等しい。」エントロピー率は、ある意味で正規であることにどれだけ近いかを表す数値であり、正規である場合は丁度 1 になる(入力した文字をそのまま出力する ILFSC では、圧縮率が 1 であることも注意しておく)。LZ 圧縮アルゴリズムは漸近的に任意の ILFSC 以上の圧縮率を誇るため、任意の非正規列を圧縮することができる。
この二つの正規列の特徴付けを標語的にまとめると、正規であることは有限オートマトンで制御できない程「ランダム」である、と言える。同様に、チューリングマシンに対して「ランダム」であるという概念を考えることができる。理論的にチューリングマシンは有限オートマトンよりも高性能であるため、この概念は正規であるという概念よりも強い。