2
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Alberto
    Jul 10, 2012 at 13:57
  • $\begingroup$ I should in fact post this as a new question. $\endgroup$
    – Alberto
    Jul 10, 2012 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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