オートマトンに各時点で与える入力は,抽象的に
あるいは
の記号で表し,これらを入力記号(input symbol) と呼ぶ。
個々のオートマトンでは,それが扱うことのできる入力記号を,あらかじめ定めておいた有限種類のものに限定し,それを入力記号の有限集合
等として明示することとする.
刻々と入力される入力記号をつなぎ合わせてできる系列,例えば
などを入力記号列 (input string),あるいは入力系列 (input sequence) と呼ぶ.
出力についても同様の扱いとする.
入力記号列・出力記号列をあわせて,記号列と呼ぶ.
あらためて記号列の定義を形式的に定める.
中の記号を重複を許して有限個数並べて得られる
を,
上の記号列 (string over
) あるいは系列 (sequence over
) という.
この記号列の長さ (length) は,
を構成している記号の数
であると定義し,
で表す.
特に長さが
の記号列を空記号列 (empty stginr) または 空系列 (empty sequence) と呼び,
で表す.
は集合の項で述べた空集合
とは異なる概念であることに注意しておこう.
例えば,
は
上の記号列であり,
である.
記号列
に対して
と表したとき,記法
は
と
の連接 (concatenation) と呼ばれる演算結果を表す.
連接
は,
,
のとき
である.
記号列
において,
を
の接頭辞 (prefix),
を
の接尾辞 (suffix) という.
また
はおのおの
の部分記号列 (substring) であるという.
ここに
は空記号列
であってよく,例えば
である.
特に
であるとき,
は
の真の(proper) 接頭辞である,等という.
において,
すなわち
は同じ記号
が
個ならべられたものであるとき,
と表す場合もある.
空記号
を含めて
上で作りうるあらゆる記号列の全体からなる無限集合を
と表し,これを
のスター閉抱 (star closure) と呼ぶ.
例えば
であるとき,
である.
また
であるとき,
である.