けいしき‐げんご【形式言語】
形式言語
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/08/29 04:57 UTC 版)
形式言語(けいしきげんご、英: formal language)は、その文法(構文、統語論)が、場合によっては意味(意味論)も、形式的に与えられている(形式体系を参照)言語である。形式的でないために、しばしば曖昧さが残されたり、話者集団によって用法のうつろいゆくような自然言語に対して、プログラミング言語を含む一部の人工言語や、いわゆる機械可読な(機械可読目録を参照)ドキュメント類などの形式言語は、用法の変化に関しては厳格である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。
定義
形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列(語 word) の集合である[1]。
言及される分野
形式言語は、「人や計算機の如何なる記号変換能力から如何なる思考能力や計算能力が生まれるか」の学としての広義の数理論理学の研究対象であり、従って形式言語は、哲学・言語学・計算機科学・数学基礎論・数理心理学等々において重要な役割を演ずる。 それらの学問分野では、如何なる形式言語を研究すべきかの文法論(構文論・統辞論)や形式言語の意味論や演繹論が研究される。
形式手法という場合には、形式言語に加えて、模擬試験、検証・証明などの仕組みを込みで言う場合が有る。
自然言語への応用
自然言語を比較的単純な形式言語のモデルにあてはめて分析する言語学は、チョムスキーによって提唱された。音素や語幹などを素記号として考える。 実際の自然言語の構文規則(あるいは文法)は、文字通り自然発生的のものであり、形式言語における構文規則のように明確に規定するのは難しい。
ただ、素朴な文法論の主張は、形式言語の理論とみなすことができる。 素朴な文法論は、例えば次のようなものである。
こういう文法論はすなわち、素記号とは何かを定め、それらから文を作る構文規則を定めるのだから、まさに形式言語の理論である。
こういう形式言語論的な文法論は、実際の言語と比較することで自然言語の特徴を浮き彫りにし、自然言語のより深い理解へと導くことを可能とすることもなくはない。言語そのものではなく、言語行動の深層をなす人間精神を探るためには、むしろこういう文法論を数学化し、更に意味論・文法論を伴った論理学にまで推し進めることが有意義ともいえよう。
脚注
- ^ 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 という用語の語源は自然数の計算可枚挙な集合の場合と同じである。
※この「形式言語」の解説は、「計算可能関数」の解説の一部です。
「形式言語」を含む「計算可能関数」の記事については、「計算可能関数」の概要を参照ください。
「形式言語」の例文・使い方・用例・文例
形式言語と同じ種類の言葉
- 形式言語のページへのリンク