Suppose we have:

$$A\text{ }\colon=\{x, y, z\}$$

$$M\text{ }\colon=\text{some DFA using A}$$

$$S\text{ }\colon=xyzxyzxyz$$

Intuitively, one might say $S$ is fed to $M$ on a per-character basis.

This means that somehow we have an undisclosed mechanism that can tell where a symbol starts and ends.

One might say, simply use the maximum valid substring similar to how Lexers tokenise plaintext. To that I say, suppose instead that we defined $A$ as: $$A\text{}\colon= \{x, xx, xxx\}$$

Now we have 3 unique symbols, that, as it so happens, using the maximum valid substring will yield in a restriction to what our our $M$ can actually process, because any string longer than 2 characters will always be assumed to start with $xxx$ rather than perhaps, $x$ and $xx$.

One way I see around this is to actually have a character synonymous to a symbol. That is, $x$ and $xxx$ (from $A$) are both a single character each.



In the case my question is unclear:

The extended transition function is defined so as to extend the processable input of a DFA from simply one alphabetic character at a time, to an arbitrary amount. Usually we go about defining it as follows for a string wa:

$$\hat{δ}(q,w) = δ(\hat{δ}(q, x), a)$$

My issue is: What is converting the input from a string to a partition? Whatever this object may be, it has to follow some lexing rules, does it not? Are there any conventions that go about this?


2 Answers 2


The transition function of a DFA has the type $\delta : (Q \times \Sigma) \rightarrow Q$. That is, it's a function that takes a state (from the set of states) and a symbol (from the set of symbols) and returns another state.

This function doesn't have to know anything about tokenization. It's given a single symbol, and that's all it cares about.

Similarly, the input to a DFA is generally defined to be an ordered series of symbols: this is what "a string over the alphabet $\Sigma$" means mathematically. If it helps, think of it as a "list" rather than a "string" in programming terms. So if the alphabet were $\{x, xx, xxx\}$, then the input might look something like $[x, xx, xxx, x, xx, xxx, x, xx, xxx]$. No ambiguity there.

In practice, most real-world DFA implementations (like foma) do have to care about tokenizing. But the details of how to do that are up to the implementation; the definition of a DFA doesn't care one way or the other.

  • $\begingroup$ "No ambiguity there" I agree, if we neatly pre-partition the input string like that always, there will never be ambiguity. Do you think this clashes with the definition we regularly use for the string transition function? All definitions for it that I've seen use a variant like $wa$ where $a$ is an alphabetic symbol, and $w$ is the substring of the initial input $s$ without the tailing $a$. So in short, the definition I regularly see for $\hat{\delta}$ is ambiguous, in my opinion, and should instead accept a pre-partitioned string, and not leave it up in the air on how $a$ was detached. $\endgroup$ Jun 27, 2020 at 18:08
  • 2
    $\begingroup$ @Novicegrammer A "string", as a mathematical object, is an ordered sequence of symbols. Thinking of it as a list instead might be helpful, because the mathematical object is defined to have no ambiguities in it (unlike the real-world objects we also call "strings"). $\endgroup$
    – Draconis
    Jun 27, 2020 at 18:20
  • $\begingroup$ So a mathematical string, is an object in which "what's the last symbol?" is a non-ambiguous question! I see, thank you, this changes everything. $\endgroup$ Jun 27, 2020 at 18:25
  • $\begingroup$ @Novicegrammer Exactly. In a mathematical string you can always get the first or last (or $i$th) symbol unambiguously. Actually this is true for many (but not all) implementations of strings as well. $\endgroup$ Jun 27, 2020 at 20:38

Your $A$ (usually called $\Sigma$) are the letters in languages. Obviously, a letter cannot be compromised of other letters. This means that you are not allowed to have $xxx\in A$, as it simply not one letter - but rather a word of 3 letters.

It does not really matter how you name the elements in $A$, and as far as we are concerned, the naming is only meaningful for humans - so pick something you will be able to interpret properly.

A DFA will think of every element in $A$ as a different letter and the naming only affects how us humans read it

  • $\begingroup$ $xxx \in A$ isn't a word, it is a single letter despite it looking like a word. This is exactly the issue that made me ask this question: Something has to "run" the automata, and that something has to know how to correctly determine where symbols start and end. $\endgroup$ Jun 27, 2020 at 16:39
  • $\begingroup$ Nothing has to "run" the automata - its a pure mathematical object. The names for the letters in $A$ are just for humans to be able to read it. The DFA doesnt really care how you called your letter, as long as its really a single letter. $\endgroup$
    – nir shahar
    Jun 27, 2020 at 16:48
  • $\begingroup$ I disagree, mathematicians compile and execute the language of mathematics all the time. Learning English turns you into an English lexer, parser, and interpreter. Why are DFAs any different? $\endgroup$ Jun 27, 2020 at 16:57
  • $\begingroup$ Furthermore, saying that DFAs don't care about what the letters are named, I actually agree with. They're just identifiers that represent mathematical objects, regardless of what they could be. But the problem is, the transition function of DFAs is defined on a per-letter basis. If I supply a string $S$ to a DFA $M$, something has to partition that string and break it down into sequential alphabetical symbols. $\endgroup$ Jun 27, 2020 at 16:59
  • $\begingroup$ you agree that in maths, naming a function as $f$, or $h$, or even $aaaaaaa$ doesnt make a difference in the underlying maths? Same here - the naming for letters doesnt impact the results. In both cases, the naming is just for convenience of the user - so it will be more readable. You could as well change the DFA transition functions along with the letter name, and the DFA would still be the same DFA $\endgroup$
    – nir shahar
    Jun 27, 2020 at 17:01

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.