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

メインページ > 自然科学 > 理学 > 数学 > 理論計算機科学 > オートマトン > オートマトン/第一類 > オートマトン/第一類/数学的準備/記号列

入力記号と入力記号列

オートマトンに各時点で与える入力は，抽象的に $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\neq \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 \}$ である．