2

I am having some trouble understanding what the question is asking me. Here is my understanding. We want to know whether or not there exists a DFA so that when I input a tuple $\langle D,w\rangle$, where $D$ refers to the parameters we define some DFA, and $w$ is a string, it will tell me whether or not $D$ accepts $w$.

I think it is not possible. Any such DFA we construct has a pumping length which differs from the pumping length of any random DFA. However I'm not sure why this contradicts the existence of a universal finite automaton. Any help would be appreciated.

quanticbolt
  • 1,746
  • I am a bit suspicious about your question for two reasons. First, your definition departs from the usual definition of the universal automaton, given in the seventies (this one exists and is finite). Secondly, what is the alphabet in your definition of a universal automaton? – J.-E. Pin May 28 '19 at 08:37
  • Well, looks like an interesting question whether or not there is a universal finite state automaton. – Wuestenfux Jun 04 '19 at 07:58
  • Hint: think about the number of states. – ShyPerson Jun 19 '19 at 04:29

0 Answers0