0
$\begingroup$

This problem is from an exercise sheet so it would be nice if you could guide me to the solution.

The problem: For $ k \in \mathbb{N}\setminus\{0\}$ let $$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$$ be the set of words with have at the k-last Position a 1.

(a) How many Myhill-Nerode-equivalence classes does $L_k$ have? Prove your answer.

(b) Construct an minimal DFA for $L_2$ from the equivalence classes.

(c) How many states does a minimal NFA for $L_k$ have? Prove your answer.

What I have:

a) I am pretty clueless, how to approach this problem. I tried to find classes for $k=1, k=2, k=3$ from which I think the amount as a function of k would be $2^k$. But I don't know how to continue.

b) Is pretty easy in comparision, I just added it for the sake of completeness.

c) I think with a) this would be much easier. Because the minimal amount of states is equivalent to the amount of NM classes. But for that I first need a).

Thank you in advance for any advice!

$\endgroup$
0
1
$\begingroup$

First, I think you have to review the Myhill Nerode Theorem and its relationship to the states of finite automata. You seem to think the number of equivalence classes is the same as the number of states in the minimal NFA, but it's actually the same as the number of states in the minimal DFA.

As a side note, minimization of NFAs is apparently much trickier than minimization of DFAs, so in an introductory formal languages class, you're not going to hear much about minimal NFAs (except in cases like this, where it's straight forward).

So this means it's parts (a) and (b) that are closely related.

As this is a worksheet question, I'll try to only give a guiding hint, rather than a straight-out answer.

The key thing (at least in my opinion) is to realise that each language $L_{k}$ is that it is only really concerned with the last $k$ symbols in the string. So the number of equivalence classes is closely related to this, and the proof that the obvious guess here works is informed by this observation.

This same observation is what gives the minimal DFA (unsurprisingly, as the equivalence classes exactly correspond to the states!). As the DFA doesn't know when the end of the string is coming up, one way you can think of it is as a little sliding window algorithm, and you should be able to relate the states, transitions and equivalence classes in terms of moving this window along one symbol.

To get the minimal NFA, lean on the nondeterminism. What is the piece of information that the DFA doesn't have that you can just nondeterministically guess?

$\endgroup$
1
  • $\begingroup$ Thank you for this explicit answer! I now noticed how c) is not so closesly related to a) as I thought. For a) I still need some help. I know have that only the k-long suffix of a string is of importance for L. There exist $2^k$ different suffixes. If we ommit the leading zeros to speak we have exactly the classes. I am now just struggeling on how we can now close that those are also all possible classes. b) I now could solve, thank you! And for c) I think we need k+1 states. 1 which reads the prefix and some time later jumps over to read the k-long suffix. Would this be the right idea? $\endgroup$
    – Ultor
    Nov 24 '20 at 14:47

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.