Is the set of codes of Deterministic Finite-State Automata a regular language?

Question

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?

Answer 1

This answer is, in a sense, a completely cheating approach, but it is indeed possible to encode all DFAs as strings.

We can write out a DFA by writing out its transition table. We can write out the transition table using just 0s and 1s as follows: first, write out a number of 1s equal to the number of states, then a 0. Then, write out a number of 1s equal to the number of symbols in the alphabet, then a zero. Then, write out each row of the transition table by writing out each entry as a number of 1s indicating which state should be transitioned into, then a 1.

Now, this particular encoding of a DFA is not regular. However, what we can do is the following. Consider the set of all such encodings. We can then order them in length-lex order, and then can number the DFAs produced this way 0, 1, 2, 3, 4, ..., etc. based on their ordering. In this case, we now have a bijection between $\mathbb{N}$ and the set of all DFAs. From there, we can then consider the regular language consisting of all natural numbers written out in binary. This set is definitely regular; here's a regular expression for it:

0 | 1(0|1)*

So we now have a regular language consisting of encodings of DFAs. The encoding is not at all easy to work with - you'd have to start listing off all encodings of DFAs until you found the one you were looking for - but mathematically it is well-defined.

Answer 2

DFAs can be stored in a regular way:

We assume $\#\notin \Sigma$ and define

$$L = \{\#\#e\mid e \in \{0,1\}^*\}^*\cdot\{\#s\#b\mid b \in \{0,1\}^*,s\in\Sigma\}^*\quad ,$$

which is clearly regular. Then for $w\in L$ such that $w = \#\#e_1\dots \#\#e_o\# s_1\#b_1\#\dots\#s_n\#b_n$ we define

$$p_0 = 1, p_i = \min\{r_{i-1},n\}$$ where

$$r_i = \min\{j>p_i\mid \exists k, p_i \leq k < j: \ s_j = s_k \}$$

is the index of the first symbol repetition after $p_i$. Let $\{p_1,\dots,p_k\}$ be the set definable in this way. Now we construct a DFA: The set of states will be $Q=\{1,\dots,m\}$, where $m=\max(\{k\}\cup\{\mathrm{bin}(b_i)\mid 1\leq i \leq n\})$ and for the sake of simplicity we choose $1$ as the starting state. The set of accepting states shall be $E=\{\mathrm{bin}(e_i)\mid 1\leq i \leq o\}$. By our interpretation of the string $w$, each part $\#s_{p_i}\#,\dots,\#b_{p_{i+1-1}}$ contains each $s\in\Sigma$ at most once and for each such $s$ a binary string. We'll interpret this string as target for our transition function $\delta: Q\times \Sigma \to Q$:

$$\delta(i,s)=\begin{cases}\mathrm{bin}(b_j) & \exists p_i,j: p_i\leq j < \min\{p_{i+1},n\}, s_j=s \\ 1 & \text{else}\end{cases}$$

Now $(\Sigma,Q,\delta,1,E)$ is a DFA. On the other hand it's obvious that any DFA can be sored this way (after renaming the states).

Answer 3

I have no idea, but my intuition is that you couldn't. You are basically asking if you can implement a regexp matcher with a push-down automaton, and I don't think you can... The regexp can be arbitrarily complex, so there is no way you can store all the state necessary in the push-down automaton states, so you'll need to use the push-down to store the state of where you are in the regexp (and/or the word)... And the problem with the push-down, is that you won't be able to do backtracking if you take a wrong turn in the regexp (in a normal automaton you have a state covering for each wrong turn possible, because all the possible combinations are known when you determine the number of states for the automaton, but I think that doing this in the push-down would require backtracking, and I don't think you can implement that)...