形式言語
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/08/14 01:18 UTC 版)
ナビゲーションに移動 検索に移動定義
形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列(語 word) の集合である[1]。
ただし、長さゼロの空単語(Empty Word, 記号 、、)も含む。 チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化(エンコード)し、その数値を解釈するプログラムを埋め込む必要がある。 チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。
あるチューリングマシンが存在して、言語に属するすべての語 w に対して動作させると受理状態で停止し、属さない語には受理しないようなとき、その言語はチューリング認識可能という。 また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。(この2つの違いは、一部の入力に対してチューリングマシンが停止しない場合があるかどうかである) また、チューリングマシンTMの言語 L(TM) とは、テープに w をセットしたあと、TMを動作させると受理状態に入って停止するような w の集合からなる言語(TM認識可能な言語)のことである。
この言語には以下のような演算が定義される。ここで、 と は共通のアルファベットから構成される言語であるとする。
- 「連結」 は、文字列群 から構成される。ここで、 は に含まれる文字列で、 は に含まれる文字列である。
- 「積集合」 は、 にも にも含まれる文字列の集合である。
- 「和集合」 は、 か に含まれる文字列の集合である。
- の「補集合」は、 に含まれない全ての文字列の集合である。
- 「商集合」 は、 に含まれる文字列 に対して、 に含まれる文字列 が存在するときに、全ての に相当する文字列群から構成される。
- 「クリーネスター」 は、 という形式の全文字列群から構成される。ただし、 は に含まれ、 である。注意すべきは、 の場合もあるので、空文字列 も含まれるという点である。
- 「反転」 は、 の全文字列を反転させた文字列群から構成される。
- と の「シャッフル」とは、 で表される全文字列から構成される。ここで、 で、 を連結した は に含まれる文字列であり、 を連結した は に含まれる文字列である。
モデル理論においては、言語は定数記号、関数記号、述語記号の集合である。[2]
形式文法
形式言語は、形式文法と密接な関係がある。例として、次のような文脈自由文法の構文規則があるとき、
- 名詞句 ::= 名詞 | 形容詞 名詞 | 名詞句 "を" 動詞 "ている" 名詞句
- 動詞 ::= "見"
- 名詞 ::= "猿" | "飼育員"
- 形容詞 ::= "小さい"
以下のように規則を再帰的に適用して、その言語の要素(名詞句)を列挙することができる。
- (猿 飼育員 小さい猿 小さい飼育員)
- (猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 猿を見ている飼育員 猿を見ている小さい猿 ... 小さい猿を見ている猿 ...)
- (猿 飼育員 小さい猿 小さい飼育員 猿をみている猿 ... 猿をみている猿をみている猿 ... 小さい猿を見ている猿を見ている小さい飼育員を見ている猿 ...)
...
すなわち、このような操作の任意回の繰り返しによって、その言語(文の集合)が得られる。
また、形式文法が階層をなすというチョムスキー階層は、生成する言語では言語の認識に必要な最小のオートマトンが階層をなすという形で現れる。
- ^ Micael Sipser (2005). Introduction to the Theory of Computation. ISBN 0534950973.
- ^ 坪井明人 (2011年). “数学基礎論サマースクール モデル理論入門”. 2012年2月18日閲覧。
形式言語と同じ種類の言葉
- 形式言語のページへのリンク