Finding a set that isn't in the image

33 Views Asked by At

$A_{DFA}(n)=\{M |M $ is a DFA, and $ |Q|=n\}$ , Where Q is the number of states in M.

Therefore $\bigcup_{n =0}^\infty A_{DFA}(n) \\$ is the set of all deterministic finite automatons.

Let $f:\bigcup_{n =0}^\infty A_{DFA}(n)\rightarrow \text{$\mathcal{P}(Σ^*$)}$ , build a language B so that $B∉\text{Img(f)}$.

I have been struggling with this problem for a while, mainly because I don't know where to start with buildng B.

Any hint or tip will be helpful. Thank you very much!

1

There are 1 best solutions below

4
On

Hint. The set of all deterministic finite automata is countable, but $\mathcal{P}(Σ^*)$ is not.