5
$\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$
  • $\begingroup$ I'm pretty sure I know most of the topics you are asking about, and yet I can't understand what you are trying to ask... Mind rephrasing it somehow? $\endgroup$ – user1494736 Jul 9 '12 at 19:36
  • $\begingroup$ No problem, I can try. Let $\Sigma$ be a fixed alphabet and let $DFA(\Sigma)$ be the set of all DFA's having input alphabet $\Sigma$. I would like to know whether there exists an alphabet $S$ and a function $f: DFA(\Sigma) \to S^*$ such that the range of $f$ is a regular language. In this moment I think the answer is no. However I have the impression that there exists an alphabet $S$ and a function $f: DFA(\Sigma) \to S^*$ such that the range of $f$ is a context-free language. $\endgroup$ – user1491069 Jul 10 '12 at 12:43
  • $\begingroup$ I'm sorry. The question I posted is trivial, since there exists a bijiection $f:DFA(\Sigma) \to S^∗$. I was trying to post a simpler version of what I really wanted. The real point is as follows. Let Σ be a fixed alphabet and let DFA(Σ) be the set of all DFA's having input alphabet Σ. Is there an alphabet S and a function f:DFA(Σ)→S∗ such that the set {(f(A),w):w∈L(A)} is accepted by a push-down automaton? $\endgroup$ – user1491069 Jul 10 '12 at 14:36
  • $\begingroup$ Here is a similar question about encoding trees on cstheory.SE which illuminates multiple aspects of this question. Tl;dr: which kind(s) of "cheating" do you want to allow? $\endgroup$ – Raphael Jul 18 '12 at 1:29
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does this prove too much? Does this imply that any countable language (e.g.: all languages of finite strings over finite alphabets) can be treated this way? E.g.: The fact that there exists a bijection between, say, halting TMs and $\mathbb N$ does not mean that it is actually accessible in any meaningful way. $\endgroup$ – mhum Jul 11 '12 at 2:28
  • $\begingroup$ @mhum- That's a good point. My answer was mostly to point out that there is some way of building a regular language of DFA encodings, so that you could (for example) diagonalize and prove that there must exist a nonregular language. I completely agree that this is not of much practical value. $\endgroup$ – templatetypedef Jul 11 '12 at 2:28
  • $\begingroup$ If anything, this points out the need to specify precisely what is meant by an "encoding". After all, you could have made the bijection between DFAs and finite-length binary strings instead of binary encodings of integers. Now, the accepting language is $(0|1)*$. Is this even a legitimate (never mind practical) "encoding" of DFAs? $\endgroup$ – mhum Jul 11 '12 at 3:05
  • $\begingroup$ @mhum: I guess your concern is that the bijection might not be computable (or very expensive) so that it is impossible (in practice) to perform it. See also my comment above. $\endgroup$ – Raphael Jul 18 '12 at 1:27
0
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

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

$\endgroup$

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.