Say we have a DFA like the one shown below that accepts the empty string, $\varepsilon$. enter image description here

Also suppose the functionality of this DFA has been implemented as a circuit so that an led lights up whenever an accepted word is detected as input.

While this hypothetical circuit is "idle", i.e. not receiving any a's or b's as input, is the led on? Is it appropriate to think of $\varepsilon$ as idling without real input? Is that what $\varepsilon$, an input string of length zero, represents?

As a follow up, for a circuit implementation of the next DFA, would it have an led that never turns on even while idle?

enter image description here

  • $\begingroup$ In theoretical computer science, circuits have an input of fixed length. Hence you’ll need a different circuit for each input length. For length zero, the circuit will have no inputs. $\endgroup$ – Yuval Filmus Dec 19 '18 at 6:34
  • $\begingroup$ Sorry, I'm confused. Is ε different than an input of length zero? I thought they were the same. $\endgroup$ – David Dec 19 '18 at 6:39
  • $\begingroup$ Exactly, the empty string has length zero, and is composed of zero symbols. $\endgroup$ – Yuval Filmus Dec 19 '18 at 6:40
  • $\begingroup$ I see, so then ε corresponds to a string of length zero. So, if I were to declare a variable representative of ε in some programming language, it would look like epsilon = ""? $\endgroup$ – David Dec 19 '18 at 6:42
  • $\begingroup$ furthermore, is there a difference between no input at all and an input of length zero? For example, if my DFA were a function, is there a difference between never calling it and passing an empty sting to it myDFA(epsilon = "")? $\endgroup$ – David Dec 19 '18 at 6:45

Deterministic automata over finite words (DFAs) that accept or reject a given word can be seen as finite-state machines that read elements from some alphabet $\Sigma$ and output elements from the output alphabet $\mathbb{B}$ that represent whether the word read so far is accepted by the original DFA.

Translating such finite-state machines to circuits is a classical topic in technical computer science. For instance, you could assign a bit-vector of the same length to every state and then use the Espresso logic minimizer to compute a relatively efficient circuit. Note that such circuits have memory.

Such finite-state machine come in two variants: Mealy and Moore machines. Both of them operate in discrete steps. At every step of their computation, Mealy machines first read an input character and them produce an output character. For Moore machines, it is the other way around: they first produce their output character and then read the next input character.

The answer to your question now depends on which model you use: If you translate your DFA into Moore machine form, the machine first outputs whether the word seen so far is accepted and only then looks at the next character. In the first step of its computation, it thus outputs whether the empty word is accepted. Mealy machines read the respective next character in every step and only then produce the next output. Thus, whether the empty word is accepted by the original DFA cannot be observed when looking at a run of the Mealy machine (unless you do the translation in a way that the machine always delays its output by one step, which normally increases the number of states by a factor of at most two).

The model that Yuval Filmus was referring to in his comments is one that is used in circuit complexity. There, it is looked at how large circuits need to be that categorize inputs of a fixed length into accepted and non-accepted ones. The characters of the input words are all read at the same time in this model and the circuits do not have memory.


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.