# Counting States in the trim automaton for $(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$

Preliminaries. Let $$n,m,p \in \mathbb{N}$$ with $$n,m,p > 1$$. We allow that $$p$$ could be large but still bounded by a function of $$n$$: $$p = O(2^n)$$. Let our alphabet be $$\Sigma = \{0,1\}$$, with non-empty languages $$L_1,L_2,...L_p \subseteq \Sigma^n$$ and $$L' \subseteq \Sigma^m$$. The other preliminaries are the same as the 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 1: Consider the minimal trim finite-state automaton $$A$$ for the language $$(L_1 \cup L_2) \circ L'$$. We observe that this language is also finite. Can we conclude that the number of states in $$A$$ at level $$n$$ is 1?

Question 2: Consider the minimal trim finite-state automaton $$B$$ for the language $$(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$$. We observe that this language is also finite. Can we conclude that the number of states in $$B$$ at level $$n$$ is 1?

Argument: If we let $$L = L_1 \cup L_2 \cup \ldots \cup L_p$$, the argument is similar: 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. Could the proof offered in the previous question work here as well?

Question 3: How does the number of states at level $$n$$ change if we drop the stipulation that these automata be trim and let $$\delta$$ be a total function?

• Please ask only one question per post. I suggest you ask Question 3 separately, in a separate post. I also suggest that you show your work on that.
– D.W.
Commented May 1, 2023 at 21:09

Yes, and yes. This follows from the result in your prior question, letting $$L = L_1 \cup L_2$$ or $$L = L_1 \cup \dots \cup L_p$$.