Team TripleFalcon. http://www.triplefalcon.com/

概要

 人間が認識する「あ」とか「春」などの漢字、ひらがな、英アルファベット等を一般的に文字や記号と呼んでいます。しかし情報理論全般では、事象はすべて、天文現象やニュース類も含め記号(symbol) と呼ぶことがあります。記号は抽象的な概念です。

 形式言語の分野では、記号とはなんであるか定義することはやめ、有限集合を任意に選んでそれをそれをアルファベット(alphabet) と呼ぶことにして、アルファベットの元を記号(symbol) または、文字(letter) と定義します。従って、言語は集合論上の言葉で定義します。(参照→集合

 プログラムの実装では、記号の範囲を限定するほうが普通です。例えば、ASCIIコード、JISコード等で定義された文字だけを記号や文字と呼びます。本ページは形式言語の範囲なので、プログラミングに関する文字の定義はこちらを参照してください。(参照→文字コード)

 文字に連接という演算を定義すると(単に文字を横にくっつける)、文字列(string) が作れます。文字列は文字が複数個並んだものです。もちろん文字列同士も連接できます。また、文字を1個も含まない文字列を考えることも出来、そのような文字列を空文字列といい λ と表記します。

 連接演算結合的なので文字列全体の集合は半群です。また、文字列の集合に空文字列 λを導入すると、λ を単位元とするモノイドになります。(参照→集合,モノイド)

 以下で定義しているのは、文字の連接、「あ」と「い」を連接すると「あい」になるなどの簡単な定義ばかりですが、記号法が見慣れないとややこしく感じるかもしれません。

Team TripleFalcon. http://www.triplefalcon.com/

定義

 集合 Σ を有限集合(finite set) とします。(参照→集合)

 Σ上の有限個の元 x1,x2,x3,...,xn の連接 x1x2x3...xn をΣ上の文字列といいます。

 Σ上の文字列の集合を Σ*と表記します。長さ n の文字列の集合を以下の様に Σn と定義します。

定義1) Σn
def
{x1x2x3...xn|x1,x2,x3,...,xn∈Σ}

 wが長さ n の文字列である場合、|w|=n と表記します。任意の長さの語 Σ* と Σ+ を下記の様に定義します。

定義2) Σ*
def
Σ0∪Σ1∪・・・=
i=0
i=∞
Σi
定義3) Σ+
def
Σ1∪Σ2∪・・・=
i=0
i=∞
Σi

 Σ* をΣの閉包、Σ+正閉包といいます。Σ*部分集合を Σ上の言語(langage) といいます。例えば、二進数全体の集合は、{0,1}* と表せます。十進数なら {0,1,2,3,4,5,6,7,8,9}* で表せます。

定義4) UがΣ上の言語
def
U⊂Σ*

 例えば、アルファベットΣ={a,b,c} 上の言語を考えます。例えば {aa,ab,ac} 等はΣ上の言語といえます。

Team TripleFalcon. http://www.triplefalcon.com/

語の演算

 アルファベット(alphabet) Σ上の二つの語 x と y が x=x1x2...xn ,y=y1y2...ym とします。(x1,...,xn,y1,...,ym ∈Σ , n,m≧0 です。)

 このとき、文字列 x と y が等しい ことを以下の様に定義します。

定義5) x=y
def
x1=y1 かつ x2=y2 かつ ... xn=yn かつ m=n

 文字列 x と y にも連接 xy を定義できます。

定義6) xy
def
x1x2x3...xny1y2y3...ym

 連接演算は結合的です。文字列 u,v,w に対して (uv)w=u(vw) が成立します。(自明ですね)空文字列 λは、文字を一つも持たない文字列ですから、以下が成立します。

 ∀w∈Σ* , λw=wλ=w

 従って、λ は左単位元かつ右単位元です。(参照→代数系

Team TripleFalcon. http://www.triplefalcon.com/

言語の演算

 U,V,W をΣ上の言語とします。(U,V,W⊂Σ*) 言語上にも連接演算閉包を定義します。

定義7) UV
def
{uv|u∈U , v∈V}

 言語上の文字列を繰り返し n 回つなげた文字列の集合です。

定義8) Wn
def
{w1w2w3...wn|w1,w2,w3,...,wn∈W}

 W* と W+ を下記の様に定義します。

定義9) W*
def
W0∪W1∪・・・=
i=0
i=∞
Wi
定義10) W+
def
W1∪W2∪・・・=
i=0
i=∞
Wi

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

記号(symbol)と文字列(string)と言語(language)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール