オートマトン/第一類/数学的準備/記号列

入力記号と入力記号列

オートマトンに各時点で与える入力は，抽象的に $0,1,\cdots ,$ あるいは $a,b,\cdots ,$ の記号で表し，これらを入力記号(input symbol) と呼ぶ。 個々のオートマトンでは，それが扱うことのできる入力記号を，あらかじめ定めておいた有限種類のものに限定し，それを入力記号の有限集合 $\mathrm{\Sigma }=\{0,1\}$ 等として明示することとする．

刻々と入力される入力記号をつなぎ合わせてできる系列，例えば $010,01001,\cdots$ などを入力記号列 (input string)，あるいは入力系列 (input sequence) と呼ぶ． 出力についても同様の扱いとする．

入力記号列・出力記号列をあわせて，記号列と呼ぶ．

記号列の長さ・空記号列

あらためて記号列の定義を形式的に定める．

$\mathrm{\Sigma }=\{a_1,a_2,\cdots ,a_n\}$ 中の記号を重複を許して有限個数並べて得られる $w=a_{i_1},a_{i_2},\cdots ,a_{i_n}$ を， $\mathrm{\Sigma }$ 上の記号列 (string over $\mathrm{\Sigma }$) あるいは系列 (sequence over $\mathrm{\Sigma }$) という． この記号列の長さ (length) は，$w$ を構成している記号の数 $n$ であると定義し，$|w|$ で表す．

特に長さが $0(n=0)$ の記号列を空記号列 (empty stginr) または 空系列 (empty sequence) と呼び，$\epsilon$ で表す． $\epsilon$ は集合の項で述べた空集合 $\varnothing$ とは異なる概念であることに注意しておこう．

例えば，$w=1101001$ は $\mathrm{\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$ は空記号列 $\epsilon$ であってよく，例えば $\epsilon yz=yz,x\epsilon z=xz,xy\epsilon =xy$ である． 特に $yz\ne \epsilon$ であるとき，$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$ と表す場合もある．

空記号 $\epsilon$ を含めて $\mathrm{\Sigma }$ 上で作りうるあらゆる記号列の全体からなる無限集合を ${\mathrm{\Sigma }}^{*}$ と表し，これを $\mathrm{\Sigma }$ のスター閉抱 (star closure) と呼ぶ．

例えば $\mathrm{\Sigma }=\{0,1\}$ であるとき， ${\mathrm{\Sigma }}^{*}=\{\epsilon ,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,0001,0010,\cdots \}$ である．

また $\mathrm{\Sigma }=\{a,b,c\}$ であるとき， ${\mathrm{\Sigma }}^{*}=\{\epsilon ,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,\cdots \}$ である．