Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is a regular language?

For example for Turing machines, the set of codes of Turing machines over a fixed alphabet is decidable, and we can speak of decidable sets of Turing machines (through their codes).

Of course we can also speak of regular sets of DFA's (through their codes). Is the set of all DFA's regular in this sense?

share|cite|improve this question

Since any DFA over $\Sigma$ can be described using only a finite number of symbols the set of all DFA's over $\Sigma$ is countable. Let $A_0,A_1,A_2,\ldots$ be an enumeration of all DFA's over $\Sigma$ and let $w_0,w_1,w_2,\ldots$ be an enumeration of all words of $\Sigma^*$ (for example in shortlex order). Then the mapping $A_n \mapsto w_n$ gives an encoding of DFA's as words over $\Sigma$. Its image is all of $\Sigma^*$ which is trivially regular.

share|cite|improve this answer
Sorry... what I asked is in fact trivial. I was trying to post a simpler version of what I really wanted. The real point is as follows. Let $\Sigma$ be a fixed alphabet and let $DFA(\Sigma)$ be the set of all DFA's having input alphabet $\Sigma$. Is there an alphabet $S$ and a function $f: DFA(\Sigma) \to S^*$ such that the set $\{(f(A),w) : w \in L(A)\}$ is accepted by a two-way push-down automaton? – Alberto Jul 10 '12 at 13:57
I should in fact post this as a new question. – Alberto Jul 10 '12 at 14:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.