Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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

 
discard

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.