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

概要

 言語を生成する規則を一般に文法(grammer) と呼びます。例えば、日本人が話す言語である日本語は、日本語文法に従って生成されると考えられます。同様に英語は英文法に従います。また、我々がコンピュータのために記述するプログラム言語もその文法に従います。

 言語の数学的モデルである形式言語(formal language) は、形式文法に従い生成されます。形式言語を大まかに分類すると以下の様になります。人間が話す言語の文法や、プログラムとして記述する言語の文法に一番近い近似を与えるのは、2型文法です。(参照→自然言語)

通称 生成規則 概要
0型 成句構造文法 u→v (u∈V+,v∈V*) チューリング機械で計算できない
1型 文脈依存文法 u→v (u∈V+,v∈V*,|u|≦|v|) 文脈依存言語を生成する
2型 文脈自由文法 A→w (A∈Γ,w∈V+) 自然言語やプログラム言語の近似
3型 正則文法
A→aB または A→a 
(A,B∈Γ,a∈Σ)
単純作業向け

 念のため述べると、m 型文法 と n 型文法で n≦m のとき、n 型文法は m 型文法を含んでいます。つまり、3 型文法は 2型文法の特殊な場合に過ぎず、2型文法は1型文法の特殊な場合に過ぎません。

 エディタやワードプロセッサなどで、検索時に正規表現を利用することがあります。正規表現で表現できる文字列の集合は、ちょうど3型文法が生成する文字列の集合に一致します。

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

定義

  Γ,Σ有限集合(finite set) とします。Γ∩Σ=φ とします。記号全体を V=Σ∪Γ と定義します。さらに、Γ+×V* の部分集合を P とします。s をΓの元とします。このとき、G=(Γ,Σ,P,S)文法(grammer) と呼びます。

定義1) G=(Γ,Σ,P,S)が文法
def


Γ,Σが有限集合 , Γ∩Σ=φ , s∈Γ
P⊂(Γ∪Σ)+×(Γ∪Σ)*

 上記の場合、Γの元を非終端記号、Σの元を終端記号、Pの元を置き換え規則、S を開始記号と呼びます。置き換え規則 (α,β)∈P を表記上 α→β と表すことが多いです。これは、文字列 α を文字列 β で置き換える様子を直感的に理解しやすいからと思われます。このときαを規則の左辺と呼び、βを右辺と呼びます。 

 書物によっては、P⊂Γ+×(Γ∪Σ)* としているものも多いです。つまり左辺に終端記号を利用してはならないという制限つきの定義です。P にそのように制限を加えても定義1と等価な文法を作ることができると証明されています。(新たに余計な非終端記号を導入する必要があるかもしれません。)

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

導出

 V* 上の関係 =>G を定義します。議論の対象 G が明らかなときは単に => と略記します。

定義2) uαv=>Guβv
def
u,v ∈(Σ∪Γ)* , (α,β)∈P

 関係 => の反射推移閉包を =*> と表記することにします。(参照→反射推移閉包) 文字列 u,v∈V* に関係 u =*> v があるとき、u から v への導出(derivation) があるといいます。

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

言語の生成

 文法 G の開始記号から導出(derivation) できる文字列(string) の集合を、G によって生成される言語といいます。表記上 L(G) と書きます。w∈Σ* であることは重要です。文字列中に Γ の元が残っている場合は、L(G) の元とはいえません。

定義3) L(G)
def
{w|w∈Σ* , S=*>Gw }

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

 以下に2型文法 G=(Γ,Σ,P,S) を定義してみます。 終端記号(Σ)と非終端記号(Γ) を以下に定義します。

 Σ={ 私 , 彼 , ジョージ , マライア, ... , 食べた , 走った , 立った , 歌った }

 Γ={ <文> , <名詞> , <動詞句> , <自動詞> , <他動詞> }

 以下に生成規則(P) を定義します。


 <文><名詞><動詞句>。 ,
 <名詞>→私    ,             <名詞>→彼 , 
 <名詞>→ジョージ ,             <名詞>→マライア ,
 <名詞>→猫    ,             <名詞>→核ボタン ,
 <名詞>→自動車
 <動詞句><名詞><他動詞> ,
 <動詞句><自動詞> , 
 <他動詞>→持った ,             <他動詞>→押した ,
 <他動詞>→殺した ,             <他動詞>→食べた ,
 <自動詞>→走った ,             <自動詞>→立った ,
 <自動詞>→歌った 

 上記のような規則を使って、どのような導出ができるか調べてみましょう。

 例1) <文> => <名詞><動詞句>。 => マライアは<動詞句>。 => マライアは<自動詞>。 => マライアは歌った。

 例2) <文> => <名詞><動詞句>。 => ジョージは<動詞句>。 => ジョージは<名詞><他動詞>。 => ジョージは核ボタンを<他動詞>。 => ジョージは核ボタンを押した。

 上記の様に、導出で遊ぶことが出来ます。以下のような文字列も作り出すことは出来ます。

 例3) 猫は自動車を食べた。 核ボタンは立った。

 非終端記号の集合を Γと表記し、終端記号の集合を Σ と表記することが多いようです。普通は Γ∩Σ=φとなるように定義します。また、多くの書物で英小文字はΣの元(終端記号)を表し、英大文字はΓの元(非終端記号)を表すように暗黙の了解があるようです。

 感じがつかめますか。

 少し工夫して置き換え規則を定義すれば不自然な文字列がでてこないように出来ます。

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

文法(grammer)

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,

終了,

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