1

Let be the following language $L_k=\{w,|w| \mbox{ is divisible by } $k$\}$

How to prove that an automata that recognizes $L_k$ has at least $k$ states?

I tried to prove it by induction :

We are going to prove that an automata that recognizes $L_k$ has at least $k$ states.

Initialization for $k=1$:

We surely need at least one state to recognize that the length of a word $w$ is severable by $1$. $(P_1)$

Let's assume that an automata that recognizes $L_k$ has at least $k$ states. $(P_k)$ for a given and fixed $k$. We are going to show that this is still true for $k+1$.

if $|w|=k+1$ ... I haven't found an idea to generalize this demonstration, do you have any tip or idea to prove that an automata that recognizes $L_k$ has at least $k$ states?

Mithlesh Upadhyay
  • 4,787
Revolucion for Monica
  • 1,511

1 Answers1

0

Induction doesn't work well for automata; the state requirements for one language do not necessarily relate to the requirements for another language, even in situations like this.

I would mimic the Myhill-Nerode minimization process here. I.e, I would argue that each state represents an equivalence class of all strings that 'end at' that state [i.e if you run the DFA on that string as input, the transition on the last character puts you in that state]. Then I would observe that two strings whose lengths are not congruent mod $k$ cannot be equivalent; since there are $k$ possible congruence classes [think 'remainders], there must be at lease $k$ states. I invite you to fill in the details.

PMar
  • 11
  • Thank you for this tip/hint ! Yet I didn't perfectly understood the following sentence : "each state represents an equivalence class of all strings that 'end at' that state": does it means they represent each state which length are equal to a given length ? – Revolucion for Monica Mar 28 '17 at 08:13