1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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 $<n$, i.e. there is a path of length $<n$ 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.

$\endgroup$
2
  • $\begingroup$ Thank you so much! $\endgroup$
    – ShyPerson
    May 11, 2023 at 3:02
  • 1
    $\begingroup$ You are welcome! $\endgroup$
    – John L.
    May 11, 2023 at 3:06

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.