0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    May 1, 2023 at 21:09

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.