2
$\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$
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$
0
$\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$

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.