YOI 765：後ろから数える言語は状態が指数で要り、前から数える言語は一次で足りる

論文765 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/765 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.23015219）。

本文のサイトの記事は、これから順に公開します。

@misc{yamagishi2026yoi765,
  author = {Yamagishi, Yuuki},
  title = {Counting from the End Needs Exponentially Many States, Counting from the Start Only Linearly Many},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/765},
  doi = {10.5281/zenodo.23015219},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

正規表現で書ける言語は、有限の記憶の機械で読める。けれど、その記憶がいくつ要るかは、同じ長さの表現でも大きく違う。後ろから数える言語と前から数える言語で、機械の状態の数を数える。新しい定理も法則も主張しない。

第一に、非決定性の機械なら、どちらも一次で足りる。「後ろから $n$ 番目が $1$」は $n+1$ 状態（第2節）。

第二に、後ろから数える言語を決定的にすると、状態はちょうど $2^{n}$ になる。部分集合構成で届く状態を $n=1$ から $12$ まで数えて、すべて $2^{n}$（第2節）。

第三に、最小化しても減らない。$n=1$ から $10$ まで、最小の決定的な機械も $2^{n}$ 状態（第2節）。

第四に、これが本稿の芯である。前から数える言語なら、決定的でも一次で足りる。最小 $n+2$ 状態で、$n=10$ では $1024$ 対 $12$、$\mathbf{85.333333}$ 倍（第3節）。

第五に、二つの機械は言語どおりに読む、$n=3$ で長さ $12$ までの $8191$ 語すべてで確かめた（第3節）。

第六に、分離子は、機械が先を見ずに一つに決めて読むか、当て推量で分かれて読んでよいかである。「正規表現は有限の記憶で読める」は、数える向きと決定性を言うまで、その記憶がいくつかが決まらない（第4節）。

キーワード：正規表現、有限オートマトン、部分集合構成、非決定性、状態の爆発、数える向き

Abstract

Languages written as regular expressions can be read by machines with finite memory. But how much memory they need differs greatly, even for expressions of the same length.Machine states are counted for a language counted from the end and one counted from the start.No new theorem or law is claimed.

First, nondeterministic machines need only linearly many states for either、“$n$-th from the end is $1$” takes $n+1$ states (Section 2).

Second, made deterministic, counting from the end reaches exactly $2^{n}$ states、subset construction’s reachable states counted for $n=1$ to $12$ all equal $2^{n}$ (Section 2).

Third, minimisation does not reduce them、for $n=1$ to $10$ the minimal deterministic machine also has $2^{n}$ states (Section 2).

Fourth, and this is the core. Counting from the start, even a deterministic machine needs only linearly many、$n+2$ states at minimum; at $n=10$, $1024$ against $12$, $\mathbf{85.333333}$ times (Section 3).

Fifth, both machines read exactly their languages、checked at $n=3$ on all $8191$ words up to length $12$ (Section 3).

Sixth, the separator is whether the machine must commit to one reading without looking ahead or may branch on guesses、“regular expressions are read with finite memory” does not say how much until the counting direction and determinism are stated (Section 4).

Keywords: regular expressions, finite automata, subset construction, nondeterminism, state explosion, counting direction

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/765/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/765 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ