0
$\begingroup$

First off, I should mention that I am a new contributor on this site and as such, please bear with me if this has been asked and answered before. I searched to the best of my ability to find similar questions and didn't find any.

The Question

Consider the definition of a deterministic finite automaton given below:

A deterministic finite automaton $M$ is an ordered $5$-tuple $ (Q,\Sigma, \delta, q_0, F)$ where:

  • $Q$ is the set of input states;
  • $\Sigma$ is a finite set of input symbols;
  • $\delta\colon Q \times \Sigma \to Q$ is the transition function;
  • $q_0$ is the initial state
  • $F$ is the set of final states

My main question is, would it be inaccurate to define $M$ as the set $ \{Q,\Sigma, \delta, q_0, F\}$ of five elements? I arrived at this question when wondering if a DFA must necessarily be ordered since n-tuples are, by definition, ordered. In other words, the tuple $(Q,\Sigma, \delta, q_0, F)$ is, by definition, different from $(Q,\Sigma, \delta, F,q_0)$. But what if we define its elements the same way as given in the definition above? Will it be a DFA? If it will, then can a DFA be instead defined as a set?

$\endgroup$
  • 1
    $\begingroup$ Would you call a set of letters a sentence? Can it be unrolled unambiguously? $\endgroup$ – Yuval Filmus Jan 23 at 17:33
  • $\begingroup$ @YuvalFilmus Ah, I see! No, I wouldn't call it a sentence. So the point of defining a DFA as 5-tuple is to ensure that all of its elements are included? Well, what about the order? Does it matter? $\endgroup$ – E.Nole Jan 23 at 17:42
  • 1
    $\begingroup$ It’s a technicality. A DFA is defined by an alphabet, a set of states, an initial state, a subset of final states, and a transition function. How you represent this information is up to you. Representing it as a set is a questionable idea - how would you know which of the five elements plays which part? There really seems nothing to gain from such a representation, but it is a lot more awkward to use. There are other possible representations - say a set of pairs (field,value), but these are basically equivalent to the standard representation. $\endgroup$ – Yuval Filmus Jan 23 at 17:48
  • $\begingroup$ @YuvalFilmus I'm still not yet clear on why it's a questionable idea. Say we represented it as a set and demanded that the set must always contain those elements. Now, since there is only one element of each type (i.e one transition function, one set of states, one final state etc.) in the set, we'd know precisely which one does what, not so? $\endgroup$ – E.Nole Jan 23 at 18:02
  • $\begingroup$ Also, if I may ask, why did you downvote? Is this question not suited to this site? $\endgroup$ – E.Nole Jan 23 at 18:02
3
$\begingroup$

A DFA fundamentally has five components, and those components aren't interchangeable. You can't freely swap the set of final states and the set of input symbols, for example, without just making a mess of everything.

The standard representation just says "those five things make a DFA". In other words, a DFA is just those five things in sequence, nothing more or less. The order matters, not because the input symbols have to come before final states, but because you need to know which is which and not get that wrong. Without an order, you wouldn't know that.

But, if you wanted to represent a DFA as some sort of dictionary instead, like $\{``Q":\{\ldots\}, ``\Sigma":\{\ldots\},\ldots\}$, that would be perfectly fine. Or a list of pairs, or really any way you like that makes it clear what's what.

$\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.