1
$\begingroup$

I am studying automata and I was wandering if there is a definition of ε-DFA automaton. Is it feasible to define it?

$\endgroup$
2
  • 3
    $\begingroup$ One of the good things about maths is that you can define whatever you want. The question is whether other people find your definition sensible and interesting. $\endgroup$
    – adrianN
    Oct 7, 2016 at 11:42
  • $\begingroup$ How would you define it? $\epsilon$-NFA without using nondeterminism besides $\epsilon$ moves? $\endgroup$
    – Evil
    Oct 9, 2016 at 15:07

2 Answers 2

5
$\begingroup$

Expanding on adrianN's comment, sure, you can define one if you want but what would be the point?

I guess the definition you have in mind is that the transition function has the form $\delta\colon Q\times (\Sigma\cup\{\varepsilon\})\to Q$. That is, for each state $q$ and each symbol $a$ in the alphabet, there's exactly one state that the automaton moves to after reading that symbol. For each state, there's also a state the automaton can move to without reading a character of input (this is $\delta(q,\varepsilon)$).

Let's briefly investigate the properties of such a machine. First, note that, if you don't want a $\varepsilon$-transition from some particular state, you can set $\delta(q,\varepsilon)=q$. We can also see that this new type of automaton accepts exactly the regular languages. It's a special kind of NFA, so it can't accept any non-regular language. And any DFA is just one of these automata where $\delta(q,\varepsilon)=q$ for every state $q$, so every regular language is accepted by an automaton of this kind.

So, what have we achieved? The advantage of DFAs is that they're easy to analyze but it can be hard to construct a DFA to accept a particular language – if you don't believe me, design an algorithm that converts arbitrary regular expressions straight to DFAs, without using NFAs as an intermediate stage. Conversely, NFAs are quite easy to construct but it can be hard to analyze what they're doing – for example, compare how annoyingly difficult it is to precisely define the language accepted by an NFA, compared to a DFA.

This new type of automaton seems to combine the disadvantages of both: requiring exactly one transition per state per symbol and at most one $\varepsilon$-transition per state means that it's still going to be fiddly to design an automaton that does what you want. But the fact that the $\varepsilon$-transitions introduce nondeterminism means that it'll be harder to analyze what's going on. Meanwhile, the power of these new automata is exactly the same as the automata we already had, so we don't seem to have gained anything.

$\endgroup$
1
$\begingroup$

I don't think so. DFAs are, by their definition, deterministic and should have deterministic transitions for every symbol of the input string. If a transition such as $\delta(q_0,\varepsilon)=q_1$ exists, the automata becomes non-deterministic because the next input symbol of the string will be passed to both $q_0$ and $q_1$ and this is what is exhibited by $\varepsilon$-NFAs.

$\endgroup$
1
  • $\begingroup$ Thank you for the explanation. I knew that was the case but only intuitevely, now I it is formally explained! $\endgroup$
    – vkoukou
    Oct 7, 2016 at 12:29

Your Answer

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

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