コンテンツにスキップ

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

出典: フリー教科書『ウィキブックス(Wikibooks)』
メインページ > 自然科学 > 理学 > 数学 > 理論計算機科学 > オートマトン > オートマトン/第一類 > オートマトン/第一類/数学的準備/記号列

入力記号と入力記号列

[編集]

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

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

入力記号列・出力記号列をあわせて,記号列と呼ぶ.


記号列の長さ・空記号列

[編集]

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

中の記号を重複を許して有限個数並べて得られる を, 上の記号列 (string over ) あるいは系列 (sequence over ) という. この記号列の長さ (length) は, を構成している記号の数 であると定義し, で表す.

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

例えば, 上の記号列であり, である.


連接

[編集]

記号列 に対して と表したとき,記法 の連接 (concatenation) と呼ばれる演算結果を表す. 連接 は, のとき である.


接頭辞・接尾辞・部分記号列

[編集]

記号列 において, の接頭辞 (prefix), の接尾辞 (suffix) という.

また はおのおの の部分記号列 (substring) であるという.

ここに は空記号列 であってよく,例えば である. 特に であるとき, の真の(proper) 接頭辞である,等という.


スター閉抱

[編集]

において, すなわち は同じ記号 個ならべられたものであるとき, と表す場合もある.

空記号 を含めて 上で作りうるあらゆる記号列の全体からなる無限集合を と表し,これを のスター閉抱 (star closure) と呼ぶ.

例えば であるとき, である.

また であるとき, である.