1
$\begingroup$

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

$\endgroup$
0

1 Answer 1

0
+100
$\begingroup$

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

Hence I am afraid this question does not make much sense.

$\endgroup$
3
  • $\begingroup$ 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^*$? $\endgroup$
    – ShyPerson
    Aug 4 at 15:05
  • $\begingroup$ Yes, of course, my typo. Also, $\forall z\in A^*$, in $A^*$, in $B^*$. Please update the question. I will update this answer accordingly. $\endgroup$
    – John L.
    Aug 4 at 18:25
  • $\begingroup$ I've tried to incorporate the edits you've suggested. In the meantime, I've seen the question does not make much sense. So I' ready to let it go. Many thanks for your work on the question. $\endgroup$
    – ShyPerson
    Aug 5 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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