  We introduce Merlin-Arthur (MA) automata where Merlin provides a certificate
at the beginning of computation and it is scanned by Arthur before reading the
input. We define Merlin-Arthur deterministic, probabilistic, and quantum finite
state automata (resp., MA-DFAs, MA-PFAs, and MA-QFAs) and postselecting MA-PFAs
and MA-QFAs (resp., MA-PostPFA and MA-PostQFA). We present several results
using different certificate lengths.
  We show that MA-DFAs use constant length certificates, and they are
equivalent to multi-entry DFAs. Thus, they recognize all and only regular
languages, but they can be exponential and polynomial state efficient over
binary and unary languages, respectively. With sublinear length certificates,
MA-PFAs can recognize several nonstochastic unary languages with cutpoint 1/2.
With linear length certificates, MA-PostPFAs can recognize these nonstochastic
unary languages with bounded error. With arbitrarily long certificates,
bounded-error MA-PostPFAs can verify every unary decidable language. With
sublinear length certificates, bounded-error MA-PostQFAs can verify several
nonstochastic unary languages. With linear length certificates, they can verify
every unary language and some NP-complete binary languages. With exponential
length certificates, they can verify every binary language.
