# Comparing automata sizes given Myhill-Nerode equivalence under a function

Consider two finite languages, $$L_A$$ over alphabet $$A$$ and $$L_B$$ over alphabet $$B$$. $$A$$ might be the same as $$B$$.

Since $$L_A$$ and $$L_B$$ are finite languages, there exist minimal acyclic deterministic finite-state automata to decide them: $$M_A$$ and $$M_B$$ respectively. So $$x \in L_A$$ iff $$M_A$$ accepts $$x$$, and $$y \in L_B$$ iff $$M_B$$ accepts $$y$$. We are also given that $$L_A$$ is bigger than $$L_B$$: $$|L_A| > |L_B|$$.

We are given a function $$f:A^*\to B^*$$. We also have the constraint that acceptance is preserved under $$f$$: $$\ \ x \in L_A$$ iff $$f(x) \in L_B$$ [modeled below by formula $$\eqref{eq1}$$]. It was established by the answer to my previous question that if two strings $$u$$ and $$v$$ map to the same Myhill-Nerode equivalence class in $$B^*$$ under $$f$$ [modeled by formula $$\eqref{eq2}$$], they map to the same equivalence class in $$A^*$$ [modeled by formula $$\eqref{eq4}$$]. This was done by showing that formula $$\eqref{eq3}$$ follows from $$\eqref{eq1}$$ and $$\eqref{eq2}$$, and $$\eqref{eq4}$$ follows from $$\eqref{eq3}$$.

$$\forall x\in A^*\ \ ((x \in L_A) \leftrightarrow (f(x) \in L_B)) \tag{1} \label{eq1}$$

$$\forall z\in A^*\ \ ((f(uz) \in L_B) \leftrightarrow (f(vz) \in L_B)) \tag{2} \label{eq2}$$

$$\forall z\in A^*\ \ ((uz \in L_A) \leftrightarrow (f(uz)\in L_B) \leftrightarrow (f(vz)\in L_B) \leftrightarrow (vz\in L_A)) \tag{3} \label{eq3}$$

$$\forall z\in A^*\ \ ((uz \in L_A) \leftrightarrow (vz \in L_A)) \tag{4} \label{eq4}$$

Questions: Given the constraints and results above, can we conclude that $$|M_A| = |M_B|$$? $$|M|$$ is the number of states in the finite automaton $$M$$. Is the reasoning below correct?

I think this would be true, because if it were not, there would be a counterexample where two strings $$u$$ and $$v$$ would map to the same state in one automaton but two different states in the other automaton.

Case 1. There are two strings $$u$$ and $$v$$ which map to one state in $$M_A$$ but two states in $$M_B$$. So $$uz \in L_A$$ and $$vz \in L_A$$ and $$f(uz) \in L_B$$, but $$f(uz) \notin L_B$$. This violates formula $$\eqref{eq1}$$ under the substitution $$x \mapsto uz$$.

Case 2. There are two strings which map to one state in $$M_B$$ but two states in $$M_A$$. So under this assumption, there would exist $$u$$ and $$v$$ such that $$f(uz) \in L_B$$ and $$f(vz) \in L_B$$ and $$\ uz \in L_A$$ but $$vz \notin L_A$$. This also violates formula $$\eqref{eq1}$$, under the substitution $$x \mapsto vz$$.

It was established by the answer to my previous question that if two strings $$u$$ and $$v$$ map to the same Myhill-Nerode equivalence class in $$B^*$$ under $$f$$ [modeled by formula (2)], they map to the same equivalence class in $$A^*$$ [modeled by formula (4)] ...
No, formula (2) does not describe the condition that two strings $$u$$ and $$v$$ in $$A^*$$ are mapped to the elements that belong to the same Myhill-Nerode equivalence class in $$B^*$$. The correct formula that describes that condition should be
$$\forall z\in B^*~((f(u)z \in L_B) \leftrightarrow (f(v)z \in L_B))$$
• Thanks for working on my question. I guess I don't understand at least one of your edits. Since $A$ and $B$ are alphabets, it might be the case that $A = \{ 0,1\}$ and $B = \{0,1\}$. So did you mean $f:A^* \rightarrow B^*$? Aug 4 at 15:05
• Yes, of course, my typo. Also, $\forall z\in A^*$, in $A^*$, in $B^*$. Please update the question. I will update this answer accordingly. Aug 4 at 18:25