|
形式言語（けいしきげんご、）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが曖昧なまま残されたり、話者集団という不特定多数によってうつろいゆくような自然言語のそれに対して、一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などは形式言語である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。 ==定義== 形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列（語 word) の集合である。 ただし、長さゼロの空単語（''Empty Word'', 記号 、、)も含む。 チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化(エンコード)し、その数値を解釈するプログラムを埋め込む必要がある。 チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。 あるチューリングマシンが存在して、言語に属するすべての語 ''w'' に対して動作させると受理状態で停止し、属さない語には受理しないようないとき、その言語はチューリング認識可能という。 また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。(この２つの違いは、一部の入力にたいしてチューリングマシンが停止しない場合があるかどうかである) また、チューリングマシンTMの言語 ''L''(TM) とは、テープに ''w'' をセットしたあと、TMを動作させると受理状態に入って停止するような ''w'' の集合からなる言語(TM認識可能な言語)のことである。 この言語には以下のような演算が定義される。ここで、 と は共通のアルファベットから構成される言語であるとする。 * 「連結」 は、文字列群 から構成される。ここで、 は に含まれる文字列で、 は に含まれる文字列である。 * 「積集合」 は、 にも にも含まれる文字列の集合である。 * 「和集合」 は、 か に含まれる文字列の集合である。 * の「補集合」は、 に含まれない全ての文字列の集合である。 * 「商集合」 は、 に含まれる文字列 に対して、 に含まれる文字列 が存在するときに、全ての に相当する文字列群から構成される。 * 「クリーネスター」 は、 という形式の全文字列群から構成される。ただし、 は に含まれ、 である。注意すべきは、 の場合もあるので、空文字列 も含まれるという点である。 * 「反転」 は、 の全文字列を反転させた文字列群から構成される。 * と の「シャッフル」とは、 で表される全文字列から構成される。ここで、 で、 を連結した は に含まれる文字列であり、 を連結した は に含まれる文字列である。 モデル理論においては、言語は定数記号、関数記号、述語記号の集合である。 これらの記号に意味を与える構造は、言語の対象外である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「形式言語」の詳細全文を読む スポンサード リンク
|