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

オートマトンに各時点で与える入力は,抽象的に 0 , 1 , ⋯ , {\displaystyle 0,1,\cdots ,} あるいは a , b , ⋯ , {\displaystyle a,b,\cdots ,} の記号で表し,これらを入力記号(input symbol) と呼ぶ。 個々のオートマトンでは,それが扱うことのできる入力記号を,あらかじめ定めておいた有限種類のものに限定し,それを入力記号の有限集合 Σ = { 0 , 1 } {\displaystyle \Sigma =\{0,1\}} 等として明示することとする.
刻々と入力される入力記号をつなぎ合わせてできる系列,例えば 010 , 01001 , ⋯ {\displaystyle 010,01001,\cdots } などを入力記号列 (input string),あるいは入力系列 (input sequence) と呼ぶ. 出力についても同様の扱いとする.
入力記号列・出力記号列をあわせて,記号列と呼ぶ.

あらためて記号列の定義を形式的に定める.
Σ = { a 1 , a 2 , ⋯ , a n } {\displaystyle \Sigma =\{a_{1},a_{2},\cdots ,a_{n}\}} 中の記号を重複を許して有限個数並べて得られる w = a i 1 , a i 2 , ⋯ , a i n {\displaystyle w=a_{i_{1}},a_{i_{2}},\cdots ,a_{i_{n}}} を, Σ {\displaystyle \Sigma } 上の記号列 (string over Σ {\displaystyle \Sigma } ) あるいは系列 (sequence over Σ {\displaystyle \Sigma } ) という. この記号列の長さ (length) は, w {\displaystyle w} を構成している記号の数 n {\displaystyle n} であると定義し, | w | {\displaystyle |w|} で表す.
特に長さが 0 ( n = 0 ) {\displaystyle 0(n=0)} の記号列を空記号列 (empty stginr) または 空系列 (empty sequence) と呼び, ε {\displaystyle \varepsilon } で表す. ε {\displaystyle \varepsilon } は集合の項で述べた空集合 ∅ {\displaystyle \varnothing } とは異なる概念であることに注意しておこう.
例えば, w = 1101001 {\displaystyle w=1101001} は Σ = { 0 , 1 } {\displaystyle \Sigma =\{0,1\}} 上の記号列であり, | w | = 7 {\displaystyle |w|=7} である.

記号列 x , y {\displaystyle x,y} に対して x y {\displaystyle xy} と表したとき,記法 x y {\displaystyle xy} は x {\displaystyle x} と y {\displaystyle y} の連接 (concatenation) と呼ばれる演算結果を表す. 連接 x y {\displaystyle xy} は, x = a 1 a 2 ⋯ a m {\displaystyle x=a_{1}a_{2}\cdots a_{m}} , y = b 1 b 2 ⋯ b n {\displaystyle y=b_{1}b_{2}\cdots b_{n}} のとき x y = a 1 a 2 ⋯ a m b 1 b 2 ⋯ b n {\displaystyle xy=a_{1}a_{2}\cdots a_{m}b_{1}b_{2}\cdots b_{n}} である.

記号列 w = x y z {\displaystyle w=xyz} において, x {\displaystyle x} を w {\displaystyle w} の接頭辞 (prefix), z {\displaystyle z} を w {\displaystyle w} の接尾辞 (suffix) という.
また x , y , z {\displaystyle x,y,z} はおのおの w {\displaystyle w} の部分記号列 (substring) であるという.
ここに x , y , z {\displaystyle x,y,z} は空記号列 ε {\displaystyle \varepsilon } であってよく,例えば ε y z = y z , x ε z = x z , x y ε = x y {\displaystyle \varepsilon yz=yz,x\varepsilon z=xz,xy\varepsilon =xy} である. 特に y z ≠ ε {\displaystyle yz\neq \varepsilon } であるとき, x {\displaystyle x} は w = x y z {\displaystyle w=xyz} の真の(proper) 接頭辞である,等という.

w = a i 1 a i 2 ⋯ a i n {\displaystyle w=a_{i_{1}}a_{i_{2}}\cdots a_{i_{n}}} において, a i 1 = a i 2 = ⋯ = a i n {\displaystyle a_{i_{1}}=a_{i_{2}}=\cdots =a_{i_{n}}} すなわち w {\displaystyle w} は同じ記号 a {\displaystyle a} が n {\displaystyle n} 個ならべられたものであるとき, w = a n {\displaystyle w=a^{n}} と表す場合もある.
空記号 ε {\displaystyle \varepsilon } を含めて Σ {\displaystyle \Sigma } 上で作りうるあらゆる記号列の全体からなる無限集合を Σ ∗ {\displaystyle \Sigma ^{*}} と表し,これを Σ {\displaystyle \Sigma } のスター閉抱 (star closure) と呼ぶ.
例えば Σ = { 0 , 1 } {\displaystyle \Sigma =\{0,1\}} であるとき, Σ ∗ = { ε , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 , 0000 , 0001 , 0010 , ⋯ } {\displaystyle \Sigma ^{*}=\{\varepsilon ,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,0001,0010,\cdots \}} である.
また Σ = { a , b , c } {\displaystyle \Sigma =\{a,b,c\}} であるとき, Σ ∗ = { ε , a , b , c , a a , a b , a c , b a , b b , b c , c a , c b , c c , a a a , a a b , a a c , a b a , a b b , a b c , a c a , a c b , a c c , b a a , b a b , ⋯ } {\displaystyle \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 \}} である.