Formal languages and finite observation

Dyck residuals and observational exposure

A generalized Dyck prefix is remembered exactly by its unmatched stack—or by failure. Its finite quotients illustrate a broader theorem: an action can be represented at every finite resolution precisely when its loss of observational depth is uniformly bounded.

FPRD-D18 · definition

The exact state of a Dyck prefix

Fix $k\ge1$ bracket types and any finite set of neutral symbols. A live state is a finite word $s=i_1\cdots i_h\in[k]^*$ listing unmatched opener types from bottom to top. Add one absorbing failure state $\bot$ . An opener pushes its type; a matching closer pops; a mismatching or underflowing closer enters failure; a neutral symbol does nothing.

The future language of a live stack is $K_s=\{w:\operatorname{run}(s,w)=\varepsilon\}$ , while $K_\bot=\varnothing$ . If $s=i_1\cdots i_h$ , its canonical completion is $\overline{s}=c_{i_h}\cdots c_{i_1}$ .

K_s=D_{k,\ell}\,c_{i_h}D_{k,\ell}\cdots c_{i_1}D_{k,\ell}.

FPRD-T34 · theorem

Stacks are exactly the left residuals

Theorem. Every left residual of the generalized Dyck language is exactly one $K_s$ or $K_\bot$ . All these residuals are reachable and pairwise distinct.

Reading a prefix from the empty stack gives the residual attached to the resulting state. Conversely, every stack is reached by its sequence of openers. Its canonical completion accepts from that stack and separates it from every incompatible state.

Let $\operatorname{sep}(K,H)$ be the shortest length of a word on which two future languages disagree. For distinct live stacks,

\operatorname{sep}(K_s,K_t)=\min(|s|,|t|), \qquad \operatorname{sep}(K_s,K_\bot)=|s|.

Thus $d(K,H)=2^{-\operatorname{sep}(K,H)}$ is an ultrametric. Openers contract distances by one half, neutrals preserve them, and closers expand them by at most two.

For at least two bracket types, the symbol actions give the faithful polycyclic transition monoid in the stated execution convention. The one-type case is the bicyclic specialization and generates no zero.

FPRD-T35 · theorem

Finite shadows recover the exact dynamic

At depth $N$ , retain every stack of height at most $N$ and merge all deeper stacks together with failure into one tail class:

X_{k,N}=\{s\in[k]^*:|s|\le N\}\sqcup\{\mathrm{tail}_N\}, \qquad |X_{k,N}|=1+\sum_{h=0}^{N}k^h.

Theorem. The inverse limit of these finite shadows contains exactly the finite live stacks and failure. It introduces no infinite-stack states.

A coherent thread either eventually names one finite stack or remains in every tail, which is failure. A word of length $r$ acts naturally from level $N+r$ to level $N$ . The shift cannot generally be removed: at level $N$ , a stack of height $N+1$ and failure coincide, but one matching closer distinguishes their images.

FPRD-D19 · definition

How much extra observation does an action expose?

Let $X$ be compact Hausdorff and let $q_N:X\to X_N$ be compatible, continuous surjections onto finite discrete sets that jointly separate points. The tower is complete: its coherent finite views reconstruct $X$ exactly.

An action $F:X\to X$ has exposure at most $e$ when, for every $N$ ,

q_{N+e}(x)=q_{N+e}(y) \quad\Longrightarrow\quad q_N(Fx)=q_N(Fy).

In plain terms, predicting the output through level $N$ requires no more than $e$ additional levels of input information.

An example beyond languages: reading binary digits

Think of an infinite stream of binary digits, starting at the least significant digit. These streams form the 2-adic integers $X=\mathbb Z_2$ . Write $x=\sum_{j\ge0}b_j2^j$ . Level $N$ reads its lowest $N$ digits: $q_N(x)=x\bmod 2^N$ . Level zero reads none.

Operation	Rule	Extra levels needed
Add one	$A(x)=x+1$	Exactly 0
Remove the lowest digit	$S(x)=(x-b_0)/2$	Exactly 1
Keep even-position digits	$D(x)=\sum_{j\ge0}b_{2j}2^j$	No fixed finite number

Add one. Congruence modulo $2^N$ is preserved by addition. Even an arbitrarily long carry does not change how many input digits determine these output digits. Exposure measures required information, not execution time.

Shift. Agreement on the lowest $N+1$ bits gives agreement on the lowest $N$ shifted bits. Zero exposure fails: 0 and 2 agree modulo 2, but shift to 0 and 1.

Select digits. For $N\ge1$ , the first $N$ output bits use input positions $0,2,\ldots,2N-2$ . Reading $2N-1$ bits suffices, so the map is continuous. But any proposed fixed exposure $e\ge0$ fails: take $N=e+2,\ x=0,\ y=2^{2N-2}$ . Since $2N-2=N+e$ , the inputs agree modulo $2^{N+e}$ ; their outputs differ by $2^{N-1}$ , visible modulo $2^N$ .

The observation scale matters. If level $N$ instead reads $2^N$ digits, the same selection map has exposure exactly one: the next level reads enough bits. Zero fails at level 1 with inputs 0 and 4, whose outputs are 0 and 2. This changes the meaning of a level, not the operation.

Why the setup qualifies. Binary streams form the compact Hausdorff product $\{0,1\}^{\mathbb N}$ . Truncations are continuous surjections to finite sets; they commute, separate points, and coherent truncations determine one stream. The exponentially reindexed tower has the same properties. These maps are self-maps, not asserted to be algebra homomorphisms.

Continuity gives a finite input horizon for each output horizon. Finite exposure requires one fixed number of extra levels to work at every horizon. This example explains the existing definition; no claim of a new theorem or external review is made.

FPRD-T36 · theorem

Finite exposure and shifted finite actions are equivalent

Theorem. An exact action has exposure at most $e$ exactly when there is a unique compatible family $F_N^{[e]}:X_{N+e}\to X_N$ satisfying $F_N^{[e]}q_{N+e}=q_NF$ . Conversely, every such shifted-natural family reconstructs a unique continuous action on $X$ .

Exposure makes the finite factor map well-defined; surjectivity of $q_{N+e}$ makes it unique. In the other direction, shifted naturality produces a coherent output thread, and completeness reconstructs its unique exact state.

Exposure bounds may be padded, and composition adds them. For the shortest-observation ultrametric, exposure $e$ is equivalent to a $2^e$ -Lipschitz bound.

A continuous action need not have one finite exposure bound valid at every level. The theorem characterizes bounded exposure, not all continuous maps of inverse limits.

FPRD-T37 · theorem

Language derivatives give the sharp calibration

Observe a language by its membership table on words of length at most $N$ . For a fixed word $u$ , the left derivative is $\delta_u(K)=u^{-1}K$ .

Theorem. On the carrier of all languages, $\delta_u$ has exposure at most $|u|$ , and this universal bound is sharp.

The membership table of $K$ through length $N+|u|$ determines the table of $u^{-1}K$ through length $N$ . Sharpness follows from $K=\{u\}$ and the empty language.

The completed derivative orbit of any language has the same finite images as its literal orbit and is reconstructed from them. For a regular language the tower eventually stabilizes to its finite residual automaton.

Universal sharpness on all languages does not imply sharpness on every selected invariant closure.

Scope

The residual calculation is for generalized Dyck languages, not arbitrary context-free languages.
Each finite shadow is an approximation; exact semantics requires the complete inverse limit.
Exposure is relative to a chosen observation tower.
No external or specialist review of these FPRD results is recorded.