けいしき‐げんご【形式言語】
形式言語
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 05:24 UTC 版)
形式言語（けいしきげんご、英: formal language）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが残されたり、話者集団によって用法のうつろいゆくような自然言語に対して、プログラミング言語を含む一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などの形式言語は、用法の変化に関しては厳格である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。
- ^ Micael Sipser (2005). Introduction to the Theory of Computation. ISBN 0534950973
- ^ 坪井明人 (2011年). “数学基礎論サマースクール モデル理論入門”. 2012年2月18日閲覧。
形式言語
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 07:32 UTC 版)
A と B をそれぞれアルファベットの集合 Σ と Γの上で書かれた形式言語だとしよう。A から B への多対一還元とは、次の性質を満たすような全体計算可能関数 f : Σ* → Γ* を指す。性質：「個々の単語 w が A の中にある必要十分条件が、『f(w) が B の中にあること』（即ち、 A = f − 1 ( B ) {\displaystyle A=f^{-1}(B)} ）である」。 もしそのような関数 f が存在するなら、A は B に多対一還元可能またはm-還元可能であると言い、次のように書く。 A ≤ m B . {\displaystyle A\leq _{m}B.} もし単射な多対一還元があるなら、A は B に1-還元可能または一対一還元可能であると言い、次のように書く。 A ≤ 1 B . {\displaystyle A\leq _{1}B.}
※この「形式言語」の解説は、「多対一還元」の解説の一部です。
「形式言語」を含む「多対一還元」の記事については、「多対一還元」の概要を参照ください。
形式言語
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/24 18:27 UTC 版)
詳細は「形式言語」を参照 形式言語は形式的な定義が与えられている言語である（そのような言語は一般に「機械可読」（machine-readable）である）。（非形式的な）自然言語と同様に、形式言語にも一般に次の2つの観点が存在する。 統語論は、その言語の見た目を規定し、その言語で考えられる表現の集合である（同じものであるが形式言語の分野では「構文論」と呼ばれることが多い）。 意味論は、その言語の各表現の意味を規定する（特にプログラミング言語では、一般的に難しいといった理由もあり（プログラム意味論を参照）意味は形式的にではなく、自然言語による説明といった形で与えられることもある）。
※この「形式言語」の解説は、「形式体系」の解説の一部です。
「形式言語」を含む「形式体系」の記事については、「形式体系」の概要を参照ください。
形式言語
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/02/29 16:21 UTC 版)
詳細は「形式言語」を参照 計算可能性理論は主に形式言語を扱う。アルファベットは任意の集合である。単語はアルファベットに含まれる文字（記号=集合の元）を有限個並べたものである。同じ文字が複数回使われてもよい。例えば、2進数の文字列はアルファベット における単語である。言語は、あるアルファベットにおける全単語の集合の部分集合である。例えば、2進数表記のうち 1 を必ず3個含むものの集合はバイナリのアルファベットにおける言語である。 形式言語の重要な特性として、ある単語がある言語に属するかどうかの判定の難しさのレベルがある。ある言語に属する単語を入力として受け付ける計算可能関数を定義するには何らかの符号体系を構築しなければならない。ある言語が計算可能であるとは、あるアルファベットにおける単語 w についての計算可能関数 があり、その単語がその言語に属する場合は 、その単語がその言語に属さない場合は となることをいう。つまり、ある言語が計算可能であるとは、任意の単語がその言語に属するかどうかを正しく判定できる手続きがある場合をいう。 ある言語が計算可枚挙であるとは、計算可能関数 f があり、単語 w がその言語に属するときだけ が定義されていることをいう。enumerable という用語の語源は自然数の計算可枚挙な集合の場合と同じである。
※この「形式言語」の解説は、「計算可能関数」の解説の一部です。
「形式言語」を含む「計算可能関数」の記事については、「計算可能関数」の概要を参照ください。
「形式言語」の例文・使い方・用例・文例
形式言語と同じ種類の言葉
- 形式言語のページへのリンク
