# Counting States in the trim automaton for $\cup_{i=1}^{p} L_i \circ L'_i$

Preliminaries. Let $$n,m,i,j,p,c \in \mathbb{N}$$ with $$n,m,i,j,p,c \geq 1$$. Let our alphabet be $$\{0,1\}$$, with non-empty languages $$L_i \subseteq \Sigma^n$$ and $$L'_i \subseteq \Sigma^m$$. The other preliminaries are the same as a previous question:

We follow the standard definition for deterministic finite-state automata except that we allow the state-transition function $$\delta$$ to be a partial function. In other words, an FSM has a finite number of states with transitions between them. We define the depth of a state $$s$$ as the length of the shortest path from the start state (at depth zero) to $$s$$.

A state $$q$$ is considered accessible if there is a path from the start state to $$q$$. A state $$q$$ is called co-accessible if there is a path from $$q$$ to a final state. Finally, an automaton is called trim if all its states are both accessible and co-accessible. This is defined here.

Question: Consider the minimal trim deterministic finite-state automaton $$A$$ for the language

$$\cup_{i=1}^{p} L_i \circ L'_i$$

We observe that this language is finite. Can we conclude that the number of states in $$A$$ at level $$n$$ is $$p$$? We are given three additional constraints:

1. All of the $$L'_i$$ are mutually disjoint, so for $$i \neq j$$, we have $$L'_i \cap L'_j = \emptyset$$.
2. Same for the $$L_i$$: for $$i \neq j$$, $$L_i \cap L_j = \emptyset$$.
3. The upper limit $$p$$ is polynomially bounded by $$n$$: $$p = O(n^c)$$ for some fixed $$c$$.

Argument: By Myhill-Nerode, the only distinguishing extensions come from the $$L'_i$$, and there are only $$p$$ mutually disjoint sets of those, so there are only $$p$$ states at level $$n$$ of the automaton. All strings not in any of the $$L_i$$ will land in the sink state, which is trimmed out of the minimal trim automaton.

Yes, the number of states in $$A$$ at level $$n$$ is $$p$$, even without the 3rd constraint. The following is a proof.

Assume $$A$$ is constructed as in this answer.

As observed in question, it is straightforward to verify that each $$L_i$$ is an equivalence class of the Nerode congruence for the given language $$L=\cup_{i=1}^{p} L_i \circ L'_i$$. Recall that for each equivalence class $$e$$, the label of any path from the initial state to state $$q_e$$ is in $$e$$. Since $$A$$ is a trim automaton for $$L$$, all paths from the initial state of length $$n$$ end at $$q_{L_i}$$ for some $$i$$.

It is enough to prove that $$q_{L_i}$$ is of depth $$n$$ for all $$i$$.

Fix an arbitrary $$i$$.

Let $$f\in L_i$$ and $$g\in L_i'$$. There is a path from the initial state to $$q_{L_i}$$ with label $$f$$ as well as a path from $$q_{L_i}$$ to an accept state with label $$g$$. The former path implies the depth of $$q_{L_i}$$ is at most $$n$$.

Towards a contradiction, suppose the depth of $$q_{L_i}$$ is $$, i.e. there is a path of length $$ from the initial state to $$q_{L_i}$$. Let $$h$$ be the label of this path.

Both $$fg$$ and $$hg$$ are in $$L$$ since each of them is the label of a path from the initial state to an accept state. The length of $$fg$$ is different from that of $$hg$$. However, all strings in $$L$$ are of the same length. This contradiction completes our proof.

• Thank you so much! Commented May 11, 2023 at 3:02
• You are welcome! Commented May 11, 2023 at 3:06