0
$\begingroup$

In The (New) Turing Omnibus by A K Dewdney, chapter 2, it says:

Moreover, for every regular expression there is an automaton which accepts the language symbolized by that expression. Thus, in a sense, regular expressions capture precisely the behavior of automata in terms of the language they accept. However, for every regular expression there are an infinite number of automata which accept that language.

But for a simple regex, e.g. a, I can think of exactly one finite automaton that corresponds to it: (start state) -a-> (accepting state). I don't see how there can be an infinite number. What am I missing?

For context, at this point in the book he has not yet introduced DFAs vs NFAs, and all examples of automata so far have been DFAs.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Note that the reverse statement is also true. This is often the case for useful models of computation: every object they describe has infinitely many description. Think of adding useless stuff; don't fall into the trap if thinking only about minimal automata. $\endgroup$
    – Raphael ♦
    Apr 17, 2017 at 11:22
  • $\begingroup$ There are also, for any regular expression, an infinite number of equivalents. The significant thing is that there is a unique minimal DFA for any regular expression. You minimise by two transformations: 1. removing all inaccessible states and 2. equating all indistinguishable ones. You can work (1) and (2) in either order. Running them in reverse generates the infinity of equivalents. Read the first couple of chapters of John Conway's Regular Algebra and Finite Machines for real insight. $\endgroup$
    – Thumbnail
    Apr 17, 2017 at 18:40

4 Answers 4

Reset to default
-1
$\begingroup$

There's at least one more DFA - consider the DFA with one state which is both the start and accepting state, and on input a transitions to itself. This accepts a* (and therefore a). If you allow ε-NFAs, it is fairly obvious that there are infinitely many, as you can always add another ε-transition before the transition leading to the accepting state. By corollary, you could add infinitely many states and transitions to any given DFA, so long as there is only one transition from the start state to a unique accepting state on input a.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. I was being silly and thinking about automata that accept only the given regex, which is not what the book said at all. $\endgroup$
    – Chris B
    Apr 17, 2017 at 9:54
  • 3
    $\begingroup$ @ChrisB No, now you're being silly. :-) When we say that an automaton accepts some language, we mean that it accepts exactly that language, and rejects all strings not in that langauge. So the construction given in the final sentence here isn't quite correct, since an automaton with only one transition from the start state to a unique accepting state could accept almost any language. $\endgroup$
    – David Richerby
    Apr 17, 2017 at 10:23
7
$\begingroup$

There are at least two ways of doing this.

The first is kind of trivial: there's no requirement that all states of an automaton be accessible from the start state. So, take your favourite automaton that accepts some language, and then add as many new states as you want, with arbitrary connections between them, as long as they're not connected to the original automaton.

A second way keeps the automaton connected. I'll give an informal description; I wrote a more formal one in response to another question. Take your favourite automaton and make $n$ copies of every state. Modify the transition function so that if, in the original automaton, $\delta(q,a)=q'$ then, in the new automaton, reading $a$ in the $i$th copy of state $q$ takes you to the $(i+1)$st copy of $q'$ (with addition modulo $n$). The start state is the first copy of the original start state; every copy of an accepting state is accepting. This isn't guaranteed to keep the automaton connected but you can delete the disconnected states and you are guaranteed to end up with an automaton with at least $n$ states.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Interesting. Started me thinking. Your second construction is a kind of unfolding the automaton, where the second component counts modulo. This made me realize that for the second component one can do any (finite) behaviour, as long as it does not contribute to acceptance. So we can unfold the first three steps by counting up to three: $0\to 1\to2\to 3\to 3\to 3 \dots$. But actually we can do product construction with any DFA (having only accepting states). $\endgroup$
    – Hendrik Jan
    Apr 17, 2017 at 14:15
  • $\begingroup$ @HendrikJan Yes. One generalization is to say that you're taking the product of your automaton $M$ with any automaton $M'$ that has no accepting states, so the resulting automaton accepts $L(M)\cup L(M') = L(M)\cup\emptyset=L(M)$. The specific instance I've used is to take $M'$ to have $n$ states that it just cycles through, regardless of the input. That has the advantage of making it easy to prove that the product automaton has lots of states accessible from its start state but it's definitily not the only possibility. $\endgroup$
    – David Richerby
    Apr 17, 2017 at 14:48
3
$\begingroup$

Consider the following automata. The notation used is $D=(Q,\ Σ,\ δ,\ q_0,\ F)$

$D_1=\{\{0,1\},\{a\},δ,0,\{1\}\}$ with $δ(0,a)=1$

$D_2=\{\{0,1,2\},\{a\},δ,0,\{1\}\}$ with $δ(0,a)=1$

$D_3=\{\{0,1,2\},\{a\},δ,0,\{1\}\}$ with $δ(0,a)=1$ and $δ(2,a)=1$

$D_4=\{\{0,1,2,3\},\{a\},δ,0,\{1\}\}$ with $δ(0,a)=1$ and $δ(2,a)=3$

$...$

they all accept just $w=a$

What is unique is the minimal DFA, but in general for a regular expression there are an infinite number of DFA which accept the language described by the regular expression.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @ChrisB Please do vote up answers that you find helpful. $\endgroup$
    – David Richerby
    Apr 17, 2017 at 10:24
0
$\begingroup$

Let me build two more automata accepting $a$ for you. Hope you got the point. You can build as much as you can.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is true, but this will give you a class of nondeterministic automata. That's valid as a general approach but the question does hint that a deterministic solution should be possible and might be preferred. $\endgroup$
    – David Richerby
    Apr 17, 2017 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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