1

$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!

Eliads
  • 359
  • Is $f$ a function that takes in DFAs and spits out a language that the DFA understands? Because then isn't it enough to exhibit a $B$ such that $B$ isn't the language of any DFA? – JuliusL33t Nov 13 '18 at 15:35
  • @JuliusL33t

    Thanks for the reply! f can spit out any language, not necessarily one that has a DFA.

     – Eliads Nov 13 '18 at 15:37

1 Answers1

1

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

J.-E. Pin
  • 40,163
  • Thanks for the reply! Yes I understand that, but I'm struggling with generating B from any given functon $f$ . – Eliads Nov 13 '18 at 15:40
  • You can prove the existence of your language $B$, but I don't think you can generate it from $f$. By the way, what is your precise definition of "generating $B$ from $f$?" – J.-E. Pin Nov 13 '18 at 15:52
  • I mean that regardless of what $f$ is I need to define the set $B$ using $f$. – Eliads Nov 13 '18 at 15:55
  • This might be difficult, if not impossible, even on a one-letter alphabet. Think of the case where $f$ is a non recursively enumerable function. – J.-E. Pin Nov 13 '18 at 16:12