2
$\begingroup$

This is a possible duplicate of the following (but not sure it answered my question):
Is it possible to support .(any symbol) or \d, \w, \W in DFA

My professor is asking for a finite automata state diagram for some language that accepts even length strings (actually it's more complicated than that, but I'm starting with that as a subset). But he didn't define the alphabet of the language (on purpose). We can assume the alphabet is definite, but I assume I can't just use an arbitrary alphabet instance.

Here is a DFA/NFA state diagram concept that I think accepts even strings (including $\epsilon$):
enter image description here

But what alphabet symbols / terminals should I put on the edges? It shouldn't be $\Sigma^*$. It shouldn't be $\epsilon$. Can I use $.$ ? Can I use a $*$ ? Can I use anything as long as I describe what it means?

EDIT - I just found the use of $*$ in these notes of an Illinois course (p.4):

$\endgroup$
5
$\begingroup$

The formal representation of an automaton is the tuple giving its state set, alphabet, transition function, start state and set of accepting states. The diagram is not a formal representation: it's just an informal way of showing what the automaton does.

As such, you can label the arrows however you want, as long as it's clear what each label means. If you think a label might be unclear, you can always add a caption to your diagram that explains what it would mean.

"." is a poor label, since it's too easy to miss. "*" is a confusing label since, in regular expressions, "*" means "any number of times", not "any symbol". Since it's quite common to see arrows in automata labelled, e.g., "$0,1$", I'd probably label the arrow "$\sigma_1, \dots, \sigma_k$" and note in the caption that $\Sigma = \{\sigma_1, \dots, \sigma_k\}$. Or you could just label the arrow "$\Sigma$".

$\endgroup$
  • 1
    $\begingroup$ I like your suggestion, as it leads into the formal definition as well ($\Sigma$ is defined formally). $\endgroup$ – delrocco Feb 4 at 16:31

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.