Formal languages and finite observation

From finite cuts to residual growth

Fixed-length prefix–suffix tables can be assembled into a single language when their literal entries agree across adjacent cuts. The resulting global quotients detect regularity, measure the largest possible finite behavior, and expose growth patterns that separate the number of behaviors from the depth needed to find them.

FPRD-D23 · definition

A uniform field of finite cuts

Let $L\subseteq\Sigma^*$ , where $\Sigma$ is finite and nonempty. For exact prefix length $m$ and future length $n$ , define the literal table

C_{m,n}(u,v)=\mathbf 1[uv\in L], \qquad u\in\Sigma^m, v\in\Sigma^n.

Adjacent cells must agree when one named symbol crosses the cut:

C_{m+1,n}(ua,v)=C_{m,n+1}(u,av).

A compatible uniform cut field retains these literal tables, combined future rows on $\Sigma^{\le N}$ , finite prefix-budget rectangles, horizon bonding maps, epsilon output, and the shifted action of each letter.

Row counts alone are insufficient. Literal prefix and suffix names are what make the diagonal compatibility equation meaningful.

FPRD-T44 · theorem

Compatible fields assemble into unique languages

Theorem. Every diagonally compatible literal cut field is the cut field of one unique language. Its joint bounded-future quotients are exactly the finite observations of that language's reachable residual orbit.

Move suffix symbols across adjacent cuts until the future axis is empty. Compatibility then determines whether each complete word belongs to the language, proving existence and uniqueness. The same calculation identifies diagonal section maps with left derivatives, which lose one level of observational depth.

There are two finite directions: how many prefixes have been reached, and how deeply each resulting residual is observed. Taking future depth first reconstructs each reached residual and then the literal residual orbit. Taking finite images in the other order gives its bounded-observation completion. The natural map from the orbit into the completion is dense and preserves the actions and Boolean output; it is onto exactly when the orbit is closed.

The completion step is the earlier FPRD-T37 theorem applied here, not a new general inverse-limit result.

FPRD-T45 · theorem

One global plateau characterizes regularity

For a prefix $u$ , let its horizon row be

\rho_N^L(u)= \bigl(\mathbf 1[uv\in L]\bigr)_{v\in\Sigma^{\le N}}, \qquad Q_N(L)=\{\rho_N^L(u):u\in\Sigma^*\}, \qquad q_L(N)=|Q_N(L)|.

Theorem. A language is regular exactly when $q_L(N)$ is bounded. Equivalently, regularity holds exactly when one adjacent global pair satisfies $q_L(N)=q_L(N+1)$ .

Horizon bonding is surjective. Equal adjacent cardinalities make the bond bijective, so no later future can split an existing class. The shifted letter actions then descend to same-level actions, producing the unique minimal residual DFA.

The word “global” is essential. A plateau among only finitely many prefixes may split later. Nor do uniformly tiny fixed-length cuts suffice: a nonregular language determined only by whether the total length is a square has one row and zero deterministic one-way bits at every individual cut, but unbounded global quotients.

FPRD-T46 · theorem

A decidable language can realize every finite behavior

Over $\Sigma=\{0,1\}$ , the ball $B_N=\Sigma^{\le N}$ contains

V_N=|B_N|=2^{N+1}-1

coordinates, so a horizon row is one of $2^{V_N}$ Boolean tables.

Theorem. For every language, $q_L(N)\le 2^{2^{N+1}-1}$ . One decidable language attains equality at every horizon simultaneously.

For each table $b\in\{0,1\}^{V_N}$ , use the root $r_{N,b}=\gamma(N+1)b$ , where $\gamma$ is the Elias gamma code. These roots are prefix-free. Membership after a root reads the requested suffix coordinate from its stored table, so every table is realized and membership remains decidable.

For any language, attaining every horizon ceiling is equivalent to its literal residual orbit being dense in the full Boolean behavior shift, and to its bounded-observation completion being that entire shift.

FPRD-T47 · theorem

Maximum diversity forces exponential access

Define $a_L(N)$ as the least prefix radius by which every row of $Q_N(L)$ has appeared. If all $2^{V_N}$ rows occur by radius $M$ , then

2^{M+1}-1\ge 2^{V_N}, \qquad\text{hence}\qquad M\ge V_N.

Theorem. Every maximum-growth language has $a_L(N)\ge V_N=2^{N+1}-1$ . For the gamma-coded language,

V_N\le a_L(N) \le V_N+2\lfloor\log_2(N+1)\rfloor+1.

The integer lower bound matters: radius $V_N-1$ contains only $2^{V_N}-1$ prefixes, one too few. The upper bound records the declared roots; it is not an exact formula because some rows may appear accidentally earlier.

FPRD-T48 · theorem

Sparse markers give an exact intermediate profile

Let $f:\mathbb N\to\mathbb N$ be strictly increasing and define

L_f=\{a^n b a^{f(n)}:n\ge0\}.

Before the marker, the residual is $A_n=\{a^{m-n}ba^{f(m)}:m\ge n\}$ . After the marker it is a singleton completion $R_r=\{a^r\}$ . Every malformed or overlong prefix has the empty residual. These three families are exhaustive, reachable, and pairwise distinct.

Theorem. At horizon $N$ ,

q_f(N)=N+2+\#\{n:f(n)\le N-1\}.

There are $N+1$ active singleton rows, one active pre-marker row for each threshold already below $N$ , and one common empty row. By choosing $f$ , the excess above the nonregular floor $N+2$ can grow unboundedly but arbitrarily slowly.

For arbitrary $f$ , no context-free, automatic, PEG, or other finite-presentation classification is claimed.

Scope

Global residual quotients and individual fixed-length cuts measure different things.
Finite-prefix observations do not certify a global plateau without an independent state bound.
The maximum-growth construction is decidable but not finitely presented by these results.
No external or specialist review of these FPRD results is recorded.