形式言語 - 暇つぶしWikipedia

形式言語

形式言語（けいしきげんご、英: formal language）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが残されたり、話者集団によって用法のうつろいゆくような自然言語に対して、プログラミング言語を含む一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などの形式言語は、用法の変化に関しては厳格である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。
定義

形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列（語 word）の集合である [1]。

L ⊂ Σ ∗ = { ⟨ σ 1 , σ 2 , . . . ⟩ 。 σ i ∈ Σ } {\displaystyle L\subset \Sigma ^{*}=\{\langle \sigma _{1},\sigma _{2},...\rangle |\sigma _{i}\in \Sigma \}}

ただし、長さゼロの空単語（Empty Word, 記号 e {\displaystyle e} 、 ϵ {\displaystyle \epsilon } 、 Λ {\displaystyle \Lambda } ）も含む。チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化(エンコード)し、その数値を解釈するプログラムを埋め込む必要がある。チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。

あるチューリングマシンが存在して、言語に属するすべての語 w に対して動作させると受理状態で停止し、属さない語には受理しないようなとき、その言語はチューリング認識可能という。また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。(この2つの違いは、一部の入力に対してチューリングマシンが停止しない場合があるかどうかである)また、チューリングマシンTMの言語 L(TM) とは、テープに w をセットしたあと、TMを動作させると受理状態に入って停止するような w の集合からなる言語(TM認識可能な言語)のことである。

この言語には以下のような演算が定義される。ここで、 L 1 {\displaystyle L_{1}} と L 2 {\displaystyle L_{2}} は共通のアルファベットから構成される言語であるとする。

「連結」 L 1 L 2 {\displaystyle L_{1}L_{2}\quad } は、文字列群 v w {\displaystyle vw} から構成される。ここで、 v {\displaystyle v} は L 1 {\displaystyle L_{1}} に含まれる文字列で、 w {\displaystyle w} は L 2 {\displaystyle L_{2}} に含まれる文字列である。

「積集合」 L 1 ∩ L 2 {\displaystyle L_{1}\cap L_{2}} は、 L 1 {\displaystyle L_{1}} にも L 2 {\displaystyle L_{2}} にも含まれる文字列の集合である。

「和集合」 L 1 ∪ L 2 {\displaystyle L_{1}\cup L_{2}} は、 L 1 {\displaystyle L_{1}} か L 2 {\displaystyle L_{2}} に含まれる文字列の集合である。

L 1 {\displaystyle L_{1}} の「補集合」は、 L 1 {\displaystyle L_{1}} に含まれない全ての文字列の集合である。

「商集合」 L 1 / L 2 {\displaystyle L_{1}/L_{2}\quad } は、 L 1 {\displaystyle L_{1}} に含まれる文字列 v w {\displaystyle vw} に対して、 L 2 {\displaystyle L_{2}} に含まれる文字列 w {\displaystyle w} が存在するときに、全ての v {\displaystyle v} に相当する文字列群から構成される。

「クリーネスター」 L 1 ∗ {\displaystyle L_{1}^{*}} は、 w 1 w 2 . . . w n {\displaystyle w_{1}w_{2}...w_{n}} という形式の全文字列群から構成される。ただし、 w i {\displaystyle w_{i}} は L 1 {\displaystyle L_{1}} に含まれ、 n ≥ 0 {\displaystyle n\geq 0} である。注意すべきは、 n = 0 {\displaystyle n=0} の場合もあるので、空文字列 ϵ {\displaystyle \epsilon } も含まれるという点である。

「反転」 L 1 R {\displaystyle L_{1}^{R}} は、 L 1 {\displaystyle L_{1}} の全文字列を反転させた文字列群から構成される。

L 1 {\displaystyle L_{1}} と L 2 {\displaystyle L_{2}} の「シャッフル」とは、 v 1 w 1 v 2 w 2 . . . v n w n {\displaystyle v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}} で表される全文字列から構成される。ここで、 n ≥ 1 {\displaystyle n\geq 1} で、 v 1 , . . . , v n {\displaystyle v_{1},...,v_{n}} を連結した v 1 . . . v n {\displaystyle v_{1}...v_{n}} は L 1 {\displaystyle L_{1}} に含まれる文字列であり、 w 1 , . . . , w n {\displaystyle w_{1},...,w_{n}} を連結した w 1 . . . w n {\displaystyle w_{1}...w_{n}} は L 2 {\displaystyle L_{2}} に含まれる文字列である。

モデル理論においては、言語は定数記号、関数記号、述語記号の集合である [2]。

L = { c 0 , c 1 , . . . } ∪ { f 0 , f 1 , . . . } ∪ { p 0 , p 1 , . . . } {\displaystyle L=\{c_{0},c_{1},...\}\cup \{f_{0},f_{1},...\}\cup \{p_{0},p_{1},...\}}
形式文法詳細は「形式文法」を参照

形式言語は、形式文法と密接な関係がある。例として、次のような文脈自由文法の構文規則があるとき、

名詞句 ::= 名詞。形容詞名詞。名詞句 "を" 動詞 "ている" 名詞句

動詞 ::= "見"

名詞 ::= "猿" 。"飼育員"

形容詞 ::= "小さい"

以下のように規則を再帰的に適用して、その言語の要素(名詞句)を列挙することができる。
(猿飼育員小さい猿小さい飼育員)

(猿飼育員小さい猿小さい飼育員猿を見ている猿猿を見ている飼育員猿を見ている小さい猿 ... 小さい猿を見ている猿 ...)

(猿飼育員小さい猿小さい飼育員猿を見ている猿 ... 猿をみている猿を見ている猿 ... 小さい猿を見ている猿を見ている小さい飼育員を見ている猿 ...)

...

すなわち、このような操作の任意回の繰り返しによって、その言語(文の集合)が得られる。

この節には独自研究が含まれているおそれがあります。

Size:44 KB
出典: フリー百科事典『ウィキペディア（Wikipedia）』
担当:undef