オートマトンに各時点で与える入力は，抽象的に 0, 1, \cdots, あるいは a, b, \cdots, の記号で表し，これらを入力記号(input symbol) と呼ぶ。
個々のオートマトンでは，それが扱うことのできる入力記号を，あらかじめ定めておいた有限種類のものに限定し，それを入力記号の有限集合 \Sigma = \{0, 1\} 等として明示することとする．
刻々と入力される入力記号をつなぎ合わせてできる系列，例えば 010, 01001, \cdots などを入力記号列 (input string)，あるいは入力系列 (input sequence) と呼ぶ．
出力についても同様の扱いとする．
入力記号列・出力記号列をあわせて，記号列と呼ぶ．
あらためて記号列の定義を形式的に定める．
\Sigma = \{a_1, a_2, \cdots, a_n\} 中の記号を重複を許して有限個数並べて得られる w = a_{i_1}, a_{i_2}, \cdots, a_{i_n} を，
\Sigma 上の記号列 (string over \Sigma) あるいは系列 (sequence over \Sigma) という．
この記号列の長さ (length) は，w を構成している記号の数 n であると定義し，|w| で表す．
特に長さが 0 (n = 0) の記号列を空記号列 (empty stginr) または 空系列 (empty sequence) と呼び，\varepsilon で表す．
\varepsilon は集合の項で述べた空集合 \varnothing とは異なる概念であることに注意しておこう．
例えば，w = 1101001 は \Sigma = \{0, 1\} 上の記号列であり，|w| = 7 である．
記号列 x, y に対して xy と表したとき，記法 xy は x と y の連接 (concatenation) と呼ばれる演算結果を表す．
連接 xy は，x = a_1 a_2 \cdots a_m，y = b_1 b_2 \cdots b_n のとき xy = a_1 a_2 \cdots a_m b_1 b_2 \cdots b_n である．
記号列 w = xyz において，x を w の接頭辞 (prefix), z を w の接尾辞 (suffix) という．
また x, y, z はおのおの w の部分記号列 (substring) であるという．
ここに x, y, z は空記号列 \varepsilon であってよく，例えば \varepsilon yz = yz, x\varepsilon z = xz, xy\varepsilon = xy である．
特に yz \ne \varepsilon であるとき，x は w = xyz の真の(proper) 接頭辞である，等という．
w = a_{i_1} a_{i_2} \cdots a_{i_n} において，a_{i_1} = a_{i_2} = \cdots = a_{i_n} すなわち w は同じ記号 a が n 個ならべられたものであるとき，w = a^n と表す場合もある．
空記号 \varepsilon を含めて \Sigma 上で作りうるあらゆる記号列の全体からなる無限集合を \Sigma^{*} と表し，これを \Sigma のスター閉抱 (star closure) と呼ぶ．
例えば \Sigma = \{0, 1\} であるとき，
\Sigma^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, \cdots \}
である．
また \Sigma = \{a, b, c\} であるとき，
\Sigma^* = \{\varepsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, \cdots \}
である．