patternMinor
Is the set of codes of Deterministic Finite-State Automata a regular language?
Viewed 0 times
thefiniteautomataregularlanguagecodesdeterministicstateset
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#2682, answer score: 4
Revisions (0)
No revisions yet.