0
$\begingroup$

From this paper,

In the proof of (Myhill-Nerode theorem) it's stated that if $L$ is a regular language and the index of $\sim_L$ is $i_L \in \mathbb{N}$ then it's both necessary and sufficient for a DFA to have $i_L$ states in order to recognize $L$ properly.

yet looking at the proof it does not seem so to me.

Can you help to point me out why by proving Myhill Nerode I know for free that a minimum DFA can't be beaten by another DFA with fewer states (i.e. it's necessary for a DFA to have at least $i_L$ states)?

$\endgroup$
0
$\begingroup$

The statement that you paraphrased is inaccurate, since there are obviously DFAs with $i_L$ states that do not recognize $L$. What the authors meant is this:

In the proof of [the Myhill-Nerode theorem] it is established that if $L$ is a regular language, and the index of $\sim_L$ is $i_L\in\Bbb N$, then it is necessary for a DFA to have at least $i_L$ states in order to recognise $L$ correctly, and $i_L$ states are sufficient in the sense that there is at least one DFA with $i_L$ states that recognises $L$ correctly.

The proof given that $(3)\Rightarrow(1)$ establishes the second claim by constructing a DFA with $i_L$ states that correctly recognises $L$. To see why the first claim is true (i.e., why $i_L$ is the minimum possible number of states), let $A$ be any DFA that recognises $L$. As noted in the proof that $(1)\Rightarrow(2)$, $\sim_A$ is a right-invariant equivalence relation on $\Sigma^*$ with finitely many classes, and $L$ is the union of some of these classes. Suppose that $x,y\in\Sigma^*$, and $x\sim_Ay$; then for each $w\in\Sigma^*$ we have $xw\in L$ iff $yw\in L$. This says that $x$ and $y$ have no distinguishing extension, which by definition means that $x\sim_Ly$. Thus, if $[x]_A$ denotes the $\sim_A$-equivalence class of $x$ and $[x]_L$ the $\sim_L$-equivalence class of $x$, we’ve just shown that $[x]_A\subseteq[x]_L$ for each $x\in\Sigma^*$. It follows that each $\sim_L$-class is a union of $\sim_A$-classes, so there are at least as many $\sim_A$-classes as there are $\sim_L$-classes.

Now go back to the definition of $\sim_A$: $x\sim_Ay$ iff inputs of $x$ and $y$ send $A$ to the same state (starting from the initial state). Thus, there is one $\sim_A$-class for each state of $A$. If $A$ has $n$ states, $\sim_A$ has $n$ equivalence classes. By definition $i_L$ is the number of $\sim_L$-classes, so $n\ge i_L$.

| cite | improve this answer | |
$\endgroup$

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.