Question

2. Count the number N(k) of all finite automata with exactly k states. Prove that in the definition of the regularity we can't restrict the num- ber or states to be less than some fixed integer

Answer 1

1)

Suppose we have k states and m input symbol

Num of ways to choose initial state = 1

Num of final states possible = 2^k (coz either choose or Not choose a state as final)

Num of different DFA with No final and no initial state : k^k*m

because let say input alphabet is a,b and for each alphabet dfa can go to any of the states.

so total num of such combination = Num of initial states * Num of different DFA with No final and no initial state * num of ways to select final state

=> 1 *  k^k*m * 2^k

==> (2^k) (k^k*m)

2) I am gonna prove this by contradiction.

Let us assume a regular languuage L={w:w mod 3=0}

And suppose we want to fix the numer of state for this language to be less than fixed integer 2.

So if there will be a finite automata with less than or equal to 2 states which accept this language then the said claim is true and if not then its false(means we found a contradiction and we can not fix thenumber of states)

I am attaching an image of such DFA which accept the above language and there is no such dfa(with less than 3 states) possible which can accept this language.

вљ а,Ь а,Ь

Hence our claim is contradicted.

Hope it helps.