翻訳と辞書
Words near each other
・ 形式的確定力
・ 形式知
・ 形式社会学
・ 形式科学
・ 形式称号
・ 形式等価判定
・ 形式美
・ 形式聴牌
・ 形式言語
・ 形式言語の階層
形式言語理論
・ 形式論
・ 形式論理
・ 形式論理学
・ 形式遺伝学
・ 形式陶冶
・ 形式電荷
・ 形影
・ 形影 菊池寛と佐佐木茂索
・ 形影一如


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

形式言語理論 : ウィキペディア日本語版
形式言語[けいしきげんご]
形式言語(けいしきげんご、)は、その文法(構文、統語論)が、場合によっては意味(意味論)も、形式的に与えられている(形式体系を参照)言語である。形式的でないために、しばしば曖昧さが曖昧なまま残されたり、話者集団という不特定多数によってうつろいゆくような自然言語のそれに対して、一部の人工言語や、いわゆる機械可読な(機械可読目録を参照)ドキュメント類などは形式言語である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。
==定義==
形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列(語 word) の集合である。
L \subset \Sigma^
* = \
ただし、長さゼロの空単語(''Empty Word'', 記号 e\epsilon\Lambda)も含む。
チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化(エンコード)し、その数値を解釈するプログラムを埋め込む必要がある。
チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。
あるチューリングマシンが存在して、言語に属するすべての語 ''w'' に対して動作させると受理状態で停止し、属さない語には受理しないようないとき、その言語はチューリング認識可能という。
また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。(この2つの違いは、一部の入力にたいしてチューリングマシンが停止しない場合があるかどうかである)
また、チューリングマシンTMの言語 ''L''(TM) とは、テープに ''w'' をセットしたあと、TMを動作させると受理状態に入って停止するような ''w'' の集合からなる言語(TM認識可能な言語)のことである。
この言語には以下のような演算が定義される。ここで、L_L_ は共通のアルファベットから構成される言語であるとする。
* 「連結」L_ L_\quad は、文字列群 vw から構成される。ここで、vL_ に含まれる文字列で、wL_ に含まれる文字列である。
* 「積集合」L_1 \cap L_2 は、L_ にも L_ にも含まれる文字列の集合である。
* 「和集合」L_1 \cup L_2 は、L_L_ に含まれる文字列の集合である。
* L_ の「補集合」は、L_ に含まれない全ての文字列の集合である。
* 「商集合」L_/L_\quad は、L_ に含まれる文字列 vw に対して、L_ に含まれる文字列 w が存在するときに、全ての v に相当する文字列群から構成される。
* 「クリーネスターL_^ は、w_w_...w_ という形式の全文字列群から構成される。ただし、w_L_ に含まれ、n \ge 0 である。注意すべきは、n = 0 の場合もあるので、空文字列 \epsilon も含まれるという点である。
* 「反転」L_^ は、L_ の全文字列を反転させた文字列群から構成される。
* L_L_ の「シャッフル」とは、v_w_v_w_...v_w_ で表される全文字列から構成される。ここで、n \ge 1 で、v_,...,v_ を連結した v_...v_L_ に含まれる文字列であり、w_,...,w_ を連結した w_...w_L_ に含まれる文字列である。
モデル理論においては、言語は定数記号、関数記号、述語記号の集合である。
L = \ \cup \ \cup \
これらの記号に意味を与える構造は、言語の対象外である。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「形式言語」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Formal language 」があります。



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.