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$

1 Answer 1

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .