3
$\begingroup$

I'm confused about how we can use the Myhill-Nerode Theorem to solve this problem, some pointers would be very helpful

Let $Σ = {\{a, b}\}$ and $C_k=Σ^*aΣ^{k-1}$

Prove that for each k, no DFA can recognize $C_k$ with fewer than $2^k$ states.

$\endgroup$

3 Answers 3

2
$\begingroup$

You need to find $2^k$ words which belong to different equivalence classes of the Myhill–Nerode relation. Put differently, you need to find a collection of $2^k$ words such that for any two of them $x \neq y$ there is a word $z$ such that $xz \in L$ and $yz \notin L$ or vice versa.

$\endgroup$
2
$\begingroup$

(I know, ancient question)

Consider the $2^k$ different strings in $\Sigma^*$ of length $k$, and consider which of those strings are equivalent to which other of those strings under the equivalence relation used in the Myhill-Nerode theorem.

Obviously, strings that end in a aren't equivalent to strings which end in b because if you attach a suffix of length $k-1$, the strings that end in a are in $C_k$ but the strings that end in b aren't.

Similarly, strings with the second-to-last letter of a aren't equivalent to strings with the second-to-last letter b because of what happens with a suffix of length $k-2$, and so on.

Therefore none of these strings are equivalent to each other, and we're done.

$\endgroup$
1
$\begingroup$

Consider the language ${C_k}$, and let $\sim_{C_k}\subseteq \Sigma\times \Sigma$ denote the Myhill-Nerode equivalence relation w.r.t to $C_k$. As the number of Myhill-Nerode equivalence classes bounds from below the size of the minimal DFA that recognizes $C_k$, it is sufficient to bound the number of Myhill-Nerode equivalnce classes from below. Specifically, we show that the relation $\sim_{C_k}$ has at least $2^k$ equivalence classes. Consider all words $w_1, w_2, \ldots, w_{2^k} \in \Sigma^k$, thus, every word $w_i$ is of length $k$ and consists only of letters from $ \Sigma = \{ a, b\}$. We claim that for all $1 \leq i < j \leq 2^k$, it holds that $[w_i]_{\sim_{C_k}} \neq [w_j]_{\sim_{C_k}}$ ($w_i$ and $w_j$ are not in the same equivalence class) , and hence there are at least $2^k$ equivalence classes:

As the words $w_i$ and $w_j$ are of length $k$, we can write them as $w_i = c_1\cdot c_2 \cdots c_{k}, w_j = d_1\cdot d_2 \cdots d_{k}$, where $c_l, d_l \in \Sigma$ for all $l\in [k]$. Recall that the words $w_i$ and $w_j$ are distinct, and let $l \leq k$ be the maximal index such that $c_l\neq d_l$. Assume w.l.o.g that $c_l = a$ and $d_l = b$. Then, any word $z$ of length $l-1$ is such that $w_i \cdot z = c_1\cdot c_2 \cdots c_l \cdot c_{l+1} \cdots c_{k} \cdot z$ has $c_l =a$ as its $k$'th letter from the end, and $w_j \cdot z = d_1\cdot d_2 \cdots d_l \cdot d_{l+1} \cdots d_{k} \cdot z$ has $d_l = b$ as its $k$'th letter from the end. Hence, every word $z$ of length $l-1$ is such that $w_i \cdot z \in C_k$, but $w_j\cdot z \notin C_k$, and thus $[w_i]_{\sim_{C_k}} \neq [w_j]_{\sim_{C_k}}$.

$\endgroup$

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.