# Counting States in the trim automaton for $L\circ L'$

Preliminaries. Let $$n,m \in \mathbb{N}$$. Let our alphabet be $$\Sigma = \{0,1\}$$, with non-empty languages $$L \subseteq \Sigma^n$$ and $$L' \subseteq \Sigma^m$$. 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.

Consider the minimal trim finite-state automaton $$A$$ for the concatenation $$L \circ L'$$. We observe that this language is also finite.

Question: Can we conclude that the number of states in $$A$$ at level $$n$$ is 1?

Argument: All the strings in $$L$$ are in the same equivalence class for the Myhill-Nerode congruence for $$L\circ L'$$, since there is no distinguishing extension for any two strings in $$L\in \Sigma^n$$. All strings not in $$L$$ will land in the sink state, which is trimmed out of the minimal trim automaton.

• Since we are dealing with nondeterministic finite automata, it is misleading to mention Myhill-Nerode theorem. Apr 26, 2023 at 17:46
• I just realized that you might mean the minimal deterministic trim automaton for $L\circ L'$. If that is the case, then the proof in my answer can be simplified by noting that there is unique state that represents the Myhill-Nerode equivalence class that is $L$ once the same claim is proved. Apr 26, 2023 at 18:07
• There can be multiple nonderministic trim automata of the minimal size for the same language. Apr 26, 2023 at 18:12
• Please clarify whether $A$ is supposed to be a deterministic automaton or a nonderministic automaton. In the referenced note, an automaton defaults to be nonderministic. Apr 26, 2023 at 18:16
• @JohnL.: I mean deterministic automata throughout. Apr 26, 2023 at 18:45

For clarity, automata are assumed deterministic and possibly incomplete in the question and this answer. A trim automaton is incomplete unless it is empty or it accepts all strings.

As your argument indicates, there must be exactly one state in $$A$$ at depth $$n$$. Here is a proof for the more general case when $$L'$$ is a nonempty finite regular language instead of a nonempty language $$\subseteq\Sigma^m$$.

##### A description of the minimum trim automaton

Any two minimum trim automata for the same language are isomorphic. Hence we use the phrase "the minimum trim automaton".

Given a nonempty regular language $$R$$, we can construct the minimum trim automaton for $$R$$ as follows. For each equivalence class $$e$$ of the Nerode congruence for $$R$$, let $$q_e$$ be a state that represents $$e$$. Let $$o$$ be the equivalence class that contains the empty string. The minimum trim automaton for $$R$$ is the $$4$$-tuple $$(\{q_e\mid\text{ there exists } w\in e\text{ and } r\in R\text{ such that }r\text{ starts with }w\},\\ \delta,\\ q_o,\\ (\{q_e\mid\text{ there exists } w\in e\text{ such that }w\in R\}),$$ where $$\delta(q_e, a)=q_{e'}$$ for all $$e, a, e'$$ such that there exists $$w\in e$$ with $$wa\in e'$$. Note that $$q_o$$ is not trimmed out because $$R$$ is not empty.

##### A proof of the existence and uniqueness of a state of depth $$n$$

We can construct the minimum trim automaton $$A$$ for $$R=L\circ L'$$ as described above.

Note that $$L\circ L'$$ consists of every string that is a string in $$L\in\Sigma^n$$ followed by a string in $$L'$$. So $$L$$ is an equivalence class of the Nerode congruence for $$L\circ L'$$. Since $$A$$ is a trim automaton for $$L\circ L'$$, all paths from the initial state of length $$n$$ end at $$q_L$$. It is enough to prove that $$q_L$$ is of depth $$n$$.

Since $$L$$ and $$L'$$ are nonempty, there is a path of length $$n$$ that starts from the initial state and ends at $$q_L$$. The depth of $$q_L$$ is at most $$n$$.

Towards a contradiction, suppose the depth of $$q_L$$ is $$, i.e. there is a path $$h$$ of length $$ from the initial state to $$q_L$$. Since all paths of length $$n$$ from the initial state end at $$q_L$$ and all strings in $$L\circ L'$$ have length at least $$n$$ and $$A$$ is a trim automaton, we can extend $$h$$ until its length becomes $$n$$, at which time it must end at $$q_L$$. Since the original $$h$$ also end at $$q_L$$, we have found a cycle in $$A$$, which implies the language accepted by $$A$$ is infinite. However, $$L\circ L'$$ is finite. This contradiction completes our proof.

No. Let $$L'=\emptyset$$ and $$n>1$$. Then $$L \circ L' = \emptyset$$, so its minimal automaton has no states at level $$n$$.

• Thanks for pointing out this counterexample. Is there a problem if we restrict the question to languages that are not empty? Apr 26, 2023 at 18:48
• I've added the restriction that the languages be non-empty. Apr 26, 2023 at 19:06