# If a DFA were implemented as a circuit, what would the empty string correspond to as input?

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

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?

• 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. – Yuval Filmus Dec 19 '18 at 6:34
• Sorry, I'm confused. Is ε different than an input of length zero? I thought they were the same. – David Dec 19 '18 at 6:39
• Exactly, the empty string has length zero, and is composed of zero symbols. – Yuval Filmus Dec 19 '18 at 6:40
• 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 = ""? – David Dec 19 '18 at 6:42
• 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 = "")? – 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.