HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is it possible to denote "any single alphabet symbol" in an FSA state diagram?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
alphabetsymbolanypossiblesinglediagramdenotestatefsa

Problem

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$):

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):

Solution

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

Context

StackExchange Computer Science Q#103835, answer score: 5

Revisions (0)

No revisions yet.