2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Since we are dealing with nondeterministic finite automata, it is misleading to mention Myhill-Nerode theorem. $\endgroup$
    – John L.
    Apr 26, 2023 at 17:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – John L.
    Apr 26, 2023 at 18:07
  • $\begingroup$ There can be multiple nonderministic trim automata of the minimal size for the same language. $\endgroup$
    – John L.
    Apr 26, 2023 at 18:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – John L.
    Apr 26, 2023 at 18:16
  • $\begingroup$ @JohnL.: I mean deterministic automata throughout. $\endgroup$
    – ShyPerson
    Apr 26, 2023 at 18:45

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks for pointing out this counterexample. Is there a problem if we restrict the question to languages that are not empty? $\endgroup$
    – ShyPerson
    Apr 26, 2023 at 18:48
  • $\begingroup$ I've added the restriction that the languages be non-empty. $\endgroup$
    – ShyPerson
    Apr 26, 2023 at 19: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.