5
$\begingroup$

When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc.

Is there a particular reason why the letter $Q$ was chosen? As in, is $Q$ the first letter of a word historically related to automata? Or was it chosen totally arbitrarily?

$\endgroup$
5
$\begingroup$

The symbol $q$ to denote the state of a finite automaton appears (for the first time??) in Moore's 1956 paper Gedanken-Experiments on Sequential Machines and since the paper became very popular, I suppose that Moore's notation has been adopted since then. Apparently, Moore didn't use any special notation for the set of states, but it you adopt $q$ for a state, $Q$ seems to be an obvious choice for the set of states.

I don't think there is any special meaning for the letter $q$ (or $Q$).

[1] E.F. Moore, Gedanken experiments on sequential machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, 129–156. Princeton University Press, 1956.

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