ファイル:Fig FA one less than three 2.png

2021-04-09T13:54:15Z

そくらてす: svg が使えなくなったの草

== 概要 ==
svg が使えなくなったの草

有限オートマトン

2021-03-16T01:26:07Z

そくらてす: Fix typos

有限オートマトン

2021-03-16T01:21:31Z

そくらてす: Fix typos

文脈自由言語

2021-03-16T00:53:14Z

そくらてす: Change some links

[[Category:形式言語理論|ブンミャクジユウゲンゴ]]
{{begin |preamble}}


{{newtheorem |type=theorem |display=定理}}
{{newtheorem |type=lemma |display=補題 |family=theorem }}
{{newtheorem |type=definition |display=定義 |family=theorem }}
{{newtheorem |type=prop |display=命題 |family=theorem }}
{{newtheorem |type=example |display=例 |family=theorem }}

<math>
\newcommand{\mathsetextension}[1]{%
\left\{ #1 \right\}%
}
\newcommand{\mathsetintension}[2]{%
\left\{ #1 \left| #2 \right.\right\}%
}
\newcommand{\mathof}[2]{%
\mathop{#1}\left(#2\right)%
}
\newcommand{\mathderiv}{\mathrel{\mathop{\Rightarrow}^{*}}}
\newcommand{\mathgen}{\rightsquigarrow}
\newcommand{\mathgenfun}[1]{\mathbf{#1}}
\newcommand{\mirrorim}[1]{\overleftarrow{#1}}
\newcommand{\emptyword}{\varepsilon}
\newcommand{\kleenecl}[1]{{#1}^{*}}
\newcommand{\interpret}[1]{[\![#1]\!]}
\newcommand{\mathautomaton}[1]{\mathcal{#1}}
\newcommand{\mathnat}{\mathbb{N}}
\newcommand{\qed}{\blacksquare}
\newcommand{\mathrelbar}{\mathrel{|}}
</math>
{{end |preamble}}
'''文脈自由言語（context-free language）'''とは文脈自由文法によって生成される形式言語である。

文脈自由文法は句構造文法の一種であるから、
文脈自由言語は[[句構造言語]]の一種である。
また、文脈自由文法は文脈依存文法の一種であるから、
文脈自由言語は[[文脈依存言語]]の一種である。

以下、項目[[形式言語]]において定められている言語上の演算などについては特に断らず用いる。

== 文脈自由言語の導入 ==
この節では文脈自由言語を定義する。
<div>
{{theorem |type=definition |name=文脈自由文法 |label=def-context-free_grammar }}
'''文脈自由文法（context-free grammar）'''とは
# 記号集合 $\Sigma$
# $\Sigma$ と互いに素な'''変数記号（variable）'''の有限集合 $V$
# '''生成規則（production rule）'''と呼ばれる有限集合 $R \subseteq V \times \kleenecl{(\Sigma \cup V)}$
# '''開始記号(start symbol)'''または'''初期記号'''と呼ばれる $S\in V$

の４つ組$(V, \Sigma, R, S)$である。
</div>

<br>

これは、[[句構造言語#句構造文法 | 句構造文法]]の一種である。また、[[文脈依存言語#文脈依存文法 | 文脈依存文法]]の一種である。

[[句構造言語]]のときと同様、$\Sigma$ の元を'''終端記号(terminal)'''、$V$ の元を'''非終端記号(non-terminal)'''と呼ぶことも多い。

以下では、元$(A, \alpha)\in R$ のことを$A\mathgen\alpha$と書く。

[[句構造言語#def-derivation | 導出]]、[[句構造言語#def-phrase_structure_lang | 生成される言語]]などは
句構造言語と同様に定義される。

'''文脈自由言語'''とは何らかの文脈自由文法によって生成される言語のことを言う。

== 文脈自由言語の例 ==
この節では文脈自由言語の例を紹介する。

<div>
{{theorem |type=example |name=Dyck言語 |label=ex-Dyck_lang }}
$V=\left\{ S \right\}$,
$\Sigma=\left\{ [, ] \right\}$,
$R=\left\{ S\mathgen\varepsilon, S\mathgen [S]S \right\}$
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
この文脈自由文法によって生成される言語 $L(G)$ を'''Dyck言語'''と呼ぶ
</div>

Dyck言語の元となる記号列とその記号列を生成する導出の列をいくつかあげる。

<math>
\begin{gather*}
S \Rightarrow \varepsilon \\
S \Rightarrow [S]S \Rightarrow [\varepsilon]S \Rightarrow [\varepsilon]\varepsilon \equiv [] \\
S \Rightarrow [S]S \Rightarrow [[]]S \Rightarrow [[]]\varepsilon \equiv [[]] \\
S \Rightarrow [S]S \Rightarrow [\varepsilon]S \Rightarrow [\varepsilon][S]S \mathderiv [\varepsilon][\varepsilon]\varepsilon \equiv [][] \\
S \Rightarrow [S]S \Rightarrow [[S]S]S \Rightarrow [[[S]S]S]S \mathderiv [[[\varepsilon]\varepsilon]\varepsilon]\varepsilon \equiv [[[]]] \\
S \Rightarrow [S]S \Rightarrow [[S]S]S \Rightarrow [[S]S][S]S \mathderiv [[\varepsilon]\varepsilon][\varepsilon]\varepsilon \equiv [[]][] \\
S \Rightarrow [S]S \Rightarrow [S][S]S \Rightarrow [S][[S]S]S \mathderiv [\varepsilon][[\varepsilon]\varepsilon]\varepsilon \equiv [][[]] \\
S \Rightarrow [S]S \Rightarrow [S][S]S \Rightarrow [S][S][S]S \mathderiv [\varepsilon][\varepsilon][\varepsilon]\varepsilon \equiv [][][]
\end{gather*}
</math>

<div>
{{theorem |type=example |name=二進表現された自然数同士の四則演算の式全体 |label=ex-arithmetic_form_lang }}
<math>
\begin{align*}
V&=\left\{ S, B, B', M, P \right\}, \\
\Sigma&=\left\{ 0, 1, +, -, \times, \div, (, ) \right\}, \\
R&=\{ S \mathgen M, S \mathgen S + M, S \mathgen S - M, M \mathgen P, M \mathgen M \times P, M \mathgen M \div P, P \mathgen B, P \mathgen ( S ), B \mathgen 0, B \mathgen 1, B \mathgen 1B', B' \mathgen 0, B' \mathgen 1, B' \mathgen 0B', B' \mathgen 1B' \}
\end{align*}
</math>
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
この文法によって生成される言語は二進表現された自然数同士の四則演算の式全体である。
</div>

二進表現された自然数同士の四則演算の式の導出の例をあげる。

<math>
\begin{align*}
S &\Rightarrow M \\
&\Rightarrow M \div P \\
&\Rightarrow M \times P \div P \\
&\Rightarrow P \times P \div P \\
&\Rightarrow (S) \times P \div P \\
&\Rightarrow (S - M) \times P \div P \\
&\Rightarrow (S + M - M) \times P \div P \\
&\Rightarrow (M + M - M) \times P \div P \\
&\Rightarrow (P + M - M) \times P \div P \\
&\Rightarrow (B + M - M) \times P \div P \\
&\Rightarrow (0 + M - M) \times P \div P \\
&\Rightarrow (0 + P - M) \times P \div P \\
&\Rightarrow (0 + B - M) \times P \div P \\
&\Rightarrow (0 + 1B' - M) \times P \div P \\
&\Rightarrow (0 + 10 - M) \times P \div P \\
&\Rightarrow (0 + 10 - P) \times P \div P \\
&\Rightarrow (0 + 10 - B) \times P \div P \\
&\Rightarrow (0 + 10 - 1) \times P \div P \\
&\Rightarrow (0 + 10 - 1) \times B \div P \\
&\Rightarrow (0 + 10 - 1) \times 1B' \div P \\
&\Rightarrow (0 + 10 - 1) \times 10B' \div P \\
&\Rightarrow (0 + 10 - 1) \times 101 \div P \\
&\Rightarrow (0 + 10 - 1) \times 101 \div B \\
&\Rightarrow (0 + 10 - 1) \times 101 \div 1 \\
\end{align*}
</math>

<div>
{{theorem |type=example |name=(命題変数が有限の)命題論理の論理式全体 |label=ex-prop_form_lang }}
<math>
\begin{align*}
V&=\left\{ S \right\}, \\
\Sigma&=\left\{ p_1, \ldots p_n, \top, \bot, \lnot, \land, \lor, \to, (, )\right\}, \\
R&=\{ S\mathgen p_1, \ldots, S\mathgen p_n, S\mathgen \top, S\mathgen \bot,
S\mathgen(\lnot S), S\mathgen(S\land S), S\mathgen(S\lor S), S\mathgen({S\to S}) \}
\end{align*}
</math>

とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
</div>

この文脈自由文法によって生成される言語 $L(G)$ は[[数理論理学の基礎・命題論理]]において定義されている命題論理の論理式全体である（ただし、命題変数の集合の濃度を有限としたときに限る）。

<div>
{{theorem |type=example |name=$0^{n}1^{n}$ という形をした記号列全体 |label=ex-counter_example_reg_lang_n }}
$V=\left\{ S \right\}$,
$\Sigma=\left\{ 0, 1 \right\}$,
$R=\left\{ S\mathgen\emptyword, S\mathgen 0S1 \right\}$
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
この文脈自由文法によって生成される言語 $L(G)$ は $0^{n}1^{n}$ （ただし、$n\in\mathnat$）という形をした記号列全体になっている。
</div>

$0^{n}1^{n}$ という形をした記号列の導出の例をいくつかあげる。

<math>
\begin{gather*}
S \Rightarrow \varepsilon \\
S \Rightarrow 0S1 \Rightarrow 0\emptyword 1 \equiv 01 \\
S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 00\emptyword 11 \equiv 0011 \\
S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 000\emptyword 111 \equiv 000111 \\
S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 0000S1111 \Rightarrow 0000\emptyword 1111 \equiv 00001111 \\
S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 0000S1111 \Rightarrow 00000S11111 \Rightarrow 00000\emptyword 11111 \equiv 0000011111
\end{gather*}
</math>

<div>
{{theorem |type=example |name=$w\mirrorim{w}$ という形をした記号列全体 |label=ex-counter_example_reg_lang_mirror }}
$V=\left\{ S \right\}$,
$\Sigma=\left\{ 0, 1 \right\}$,
$R=\left\{ S\mathgen\emptyword, S\mathgen 0S0, S\mathgen 1S1 \right\}$
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
この文脈自由文法によって生成される言語 $L(G)$ は $w\mirrorim{w}$ （ただし、$w\in \kleenecl{\Sigma}$）という形をした記号列全体になっている。
</div>

$w\mirrorim{w}$ という形をした記号列の導出の例をいくつかあげる。

<math>
\begin{gather*}
S \Rightarrow \varepsilon \\
S \Rightarrow 0S0 \Rightarrow 0\emptyword 0 \equiv 00 \\
S \Rightarrow 1S1 \Rightarrow 1\emptyword 1 \equiv 11 \\
S \Rightarrow 0S0 \Rightarrow 00S00 \Rightarrow 00\emptyword 00 \equiv 0000 \\
S \Rightarrow 0S0 \Rightarrow 01S10 \Rightarrow 01\emptyword 10 \equiv 0110 \\
S \Rightarrow 1S1 \Rightarrow 10S01 \Rightarrow 10\emptyword 01 \equiv 1001 \\
S \Rightarrow 1S1 \Rightarrow 11S11 \Rightarrow 11\emptyword 11 \equiv 1111
\end{gather*}
</math>

== Backus-Naur記法 ==
この節では'''[[Backus-Naur記法]](Backus-Naur form)'''について述べる。

=== Backus-Naur記法の導入 ===
<math>
\begin{align*}
V&=\left\{ S, A_{1}, \dots A_{n} \right\}, \\
R&=\{ S\mathgen \alpha_{00}, \dots S\mathgen \alpha_{0m_{0}}, \\
&\phantom{=\{} A_{1}\mathgen \alpha_{10}, \dots A_{1}\mathgen \alpha_{1m_{1}}, \\
&\phantom{=\{ A_{1}\mathgen \alpha_{10}, } \vdots \\
&\phantom{=\{} A_{n}\mathgen \alpha_{n0}, \dots A_{n}\mathgen \alpha_{nm_{n}} \}
\end{align*}
</math>

という、文脈自由文法 $G=(V, \Sigma, R, S)$ について、

<math>
\begin{align*}
S &::= \alpha_{00} \mathrelbar \dots \mathrelbar \alpha_{0m_{0}} \\
A_{1} &::= \alpha_{10} \mathrelbar \dots \mathrelbar \alpha_{1m_{1}} \\
\vdots \\
A_{n} &::= \alpha_{n0} \mathrelbar \dots \mathrelbar \alpha_{nm_{n}}
\end{align*}
</math>

という表記を $G$ の'''[[Backus-Naur記法]](Backus-Naur form)'''という。

この記法は、論理式の定義やプログラミング言語の定義などによく使われる。

=== BNFの例 ===
<div>
{{theorem |type=example |name=二進表現された自然数同士の四則演算の式全体 |label=ex-arithmetic_form_lang_BNF }}

[[文脈自由言語#ex-arithmetic_form_lang | 二進表現された自然数同士の四則演算の式全体]]を表すBNF記法は次のとおりである。

<math>
\begin{align*}
S &::= M \mathrelbar S + M \mathrelbar S - M \\
M &::= P \mathrelbar M \times P \mathrelbar M \div P \\
P &::= B \mathrelbar ( S ) \\
B &::= 0 \mathrelbar 1 \mathrelbar 1B' \\
B' &::= 0 \mathrelbar 1 \mathrelbar 0B'\mathrelbar 1B'
\end{align*}
</math>
</div>




== 参考文献 ==
# 新屋良磨、オートマトン理論再考、コンピュータソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3、https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
# 五十嵐喜英他、『数理情報科学シリーズ２４オートマトンと形式言語の基礎』、牧野書店、2011

== 関連項目 ==
* [[形式言語]]
* [[Backus-Naur記法]]

{| class="wikitable" style="margin: auto;"
|+ Chomsky階層
! 文法のタイプ
! 言語のクラス
! 計算モデル
|-
! タイプ0
| [[句構造言語]]
| [[Turingマシン]]
|-
! タイプ1
| [[文脈依存言語]]
| [[線形有界オートマトン]]
|-
!タイプ2
| [[文脈自由言語]]
| [[プッシュダウン・オートマトン]]
|-
!タイプ3
| [[正規言語]]
| [[有限オートマトン]]
|}

数理論理学の基礎、命題論理

2021-03-16T00:46:01Z

そくらてす: Redirect to 数理論理学の基礎・命題論理

#REDIRECT [[数理論理学の基礎・命題論理]]

自然数

2021-03-06T00:06:47Z

そくらてす: Q-rad (トーク) による編集を Alwe による直前の版へ差し戻しました

[[Category:数の集合|シゼンスウ]]
{{begin |preamble}}

{{#scite: SimpsonYokoyama13
|type=journal
|author=S. G. Simpson, and K. Yokoyama
|year=2013
|title=Reverse mathematics and Peano categoricity
|journal=Annals of Pure and Applied Logic
|volume=164
|number=3
|pages=284–293
}}

{{newtheorem |type=theorem |display=定理}}
{{newtheorem |type=lemma |display=補題 |family=theorem }}
{{newtheorem |type=definition |display=定義 |family=theorem }}
{{newtheorem |type=prop |display=命題 |family=theorem }}
{{newtheorem |type=example |display=例 |family=theorem }}

<math>
\newcommand{\mathsetextension}[1]{%
\left\{ #1 \right\}%
}
\newcommand{\mathsetintension}[2]{%
\left\{ #1 \left| #2 \right.\right\}%
}
\newcommand{\mathof}[2]{%
\mathop{#1}\left(#2\right)%
}
\newcommand{\mathnat}{\mathbb{N}}
\newcommand{\mathreal}{\mathbb{R}}
\newcommand{\qed}{\blacksquare}
\newcommand{\mathrelbar}{\mathrel{|}}
</math>
{{end |preamble}}
'''自然数'''(natural number)とは、素朴には “ $0, 1, 2, \ldots$ ” のように数えられる「数」のことである。
現代数学においてはPeanoの公理を満たす構造として自然数全体の集合 $\mathbb{N}$ を定義し、
その元のことを自然数と呼ぶ。

== Peanoの公理 ==
この節では自然数全体の集合の定義である'''Peanoの公理'''について述べる。

{{theorem |type=definition |name=Peanoの公理 |label=def-Peano }}
空でない集合 $\mathbb{N}$ 、単射写像 $s\colon \mathbb{N} \to \mathbb{N}$ と $\mathbb{N}$ の元 $0$ が
次の1、2を満たすとき $\left(\mathbb{N}, \mathop{s}, 0 \right)$ を'''自然数全体の集合'''や
'''自然数の集合'''と呼ぶ:
# $0 \notin \mathof{s}{\mathbb{N}}$;
# 任意の$X \subseteq \mathbb{N}$ について、$0 \in X $ かつ $ \mathof{s}{X} \subseteq X$ ならば、$X=\mathbb{N}$。

$\mathbb{N}$ が自然数全体の集合であるとき、$\mathbb{N}$の元は'''自然数'''と呼ばれる。

== Peanoの公理を満たす具体例 ==
この節ではPeanoの公理を満たす例をみる。

{{theorem |type=example |name=集合系による |label=ex-N_with_set }}
以下のように帰納的に定義される最小の集合系 $\mathbf{N}$ はPeanoの公理を満たす構造と考えることができる。
# 空集合 $\emptyset$ は $\mathbf{N}$ の元である。
# $n \in \mathbf{N}$ であるとき, $n \cup \left\{ n \right\} \in \mathbf{N}$。

具体的には $\mathbb{N}=\mathbf{N}$, $0=\emptyset$, $\mathop{s}(n)=n \cup \mathsetextension{n}$ とすればよい。

{{theorem |type=example |name=記号列による |label=ex-N_with_symbols }}
記号の集合 $\mathsetextension{z, s}$ 上の記号列であって、
以下のように帰納的に定義される最小の記号列の集合 $\mathbf{N}$ は
Peanoの公理を満たす構造と考えることができる。
# 記号列 $z$ は $\mathbf{N}$ の元である。
# 記号列 $\mathbf{n}$ が $\mathbf{N}$ の元であるとき、文字列 $s\mathbf{n}$ は $\mathbf{N}$ の元である。

具体的には $\mathbb{N}=\mathbf{N}$, $0=z$, $\mathop{s}(\mathbf{n})=s\mathbf{n}$ とすればよい。

== 自然数全体の一意性 ==
自然数の集合は同型を除いて一意に定まる。

== $0$ は自然数か？ ==
自然数の集合の定義には $0$ を自然数に含む流儀と $0$ を自然数に含まない流儀がある。
この節ではそのことについて述べる。

=== Mathpediaでのスタンス ===
Mathpediaにおいては「$0$ を自然数とするかどうか」について、
各分野ごとの習慣やそれぞれで行っている議論における利便性に応じて、
適宜筆者の判断に委ねることとしている。
そのためこの記事以外のMathpediaの記事においては、
'''$0$ を自然数に含まない流儀が採用されることがある'''。
個別の記事を読む際には注意されたい。

==== $0$ を自然数に含まない流儀の場合のPeano の公理 ====
$0$ を自然数に含まない流儀の場合の自然数の集合は{{ref |type=definition |label=def-Peano }}の
$0$ をすべて $1$ に書き換えれば良い。

=== この記事でのスタンス ===

この記事においては、次の観点から $0$ を含む流儀を採用した。
* Peano の公理の具体例を構成する際、$0$ を含まない流儀を採用すると不自然になる。
* 自然数の加法に単位元がほしい。
* 集合論などでは $0$ を含む流儀が普通である。

=== 落ち穂拾い ===
==== ISO 80000-2:2009 ====
数学記号について定義している国際規格であるISO 80000-2:2009 によると、

{| class="wikitable" style="margin: auto;"
! Item No.
! Sign, Symbol, expression
! Meaning, verbal equivalent
! Remarks and examples
|-
| 2-6.1
| $\mathbf{N}$
| the set of natural numbers, <br /> the set of positive integers and zero
|$\mathbf{N}=\mathsetextension{0, 1, 2, 3, \ldots}$ <br /> $\mathbf{N^{*}}=\mathsetextension{1, 2, 3, \ldots}$ <br /> Other restrictions can be indicate in an obvious way, as shown below. <br /> $\mathbf{N_{\lt 5}}=\mathsetintension{ n \in \mathbf{N} }{n \lt 5}$ <br /> The symbols $\mathrm{I\! N}$ and $\mathbb{N}$ are also used.
|}
と定義されている。日本語訳は以下のようになる。

{| class="wikitable" style="margin: auto;"
! 番号
! 記号、記号列
! 意味
! 注意および例
|-
| 2-6.1
| $\mathbf{N}$
| 自然数の集合、<br /> 正の整数およびゼロからなる集合
|$\mathbf{N}=\mathsetextension{0, 1, 2, 3, \ldots}$ <br /> $\mathbf{N^{*}}=\mathbf{N^{*}}=\mathsetextension{1, 2, 3, \ldots}$ <br /> 他の制限については以下のように表記できる。 <br /> $\mathbf{N_{\lt 5}}=\mathsetintension{ n \in \mathbf{N} }{n\lt 5}$ <br /> 記号$\mathrm{I\! N}$や$\mathbb{N}$もまた使われる。
|}

== Peano範疇性に対する逆数学 ==

Peanoシステムの範疇性定理については良く知られた事実であるが、この範疇性に対する逆数学として以下のような結果が知られている。

==== 定義（Peanoシステム） ====
$ A\subseteq\mathbb{N},i\in A,f\colon A\to A$ の組 $\langle A,i,f\rangle$ を'''システム''' (system) という。システム $\langle A,i,f\rangle$ が'''Peanoシステム''' (Peano system) であるとは、以下の条件を満たすことである。
# $i\notin\mathrm{rng}(f)$ である。
# $f$ は単射である。
# 任意の $X\subseteq A$ に対して、$i\in X$ かつ、任意の $x\in\mathbb{N}$ に対して $x\in X$ ならば $f(x)\in X$ であると仮定する。このとき $X=A$ である。

また $\langle \mathbb{N},0,\mathrm{suc}\rangle$ を標準的なPeanoシステムという。ここで $\mathrm{suc}(x):=x+1$ である。

==== 定義（同型） ====
Peanoシステム $\langle A,i,f\rangle$ が $\langle \mathbb{N},0,\mathrm{suc}\rangle$ に'''同型''' (isomorphic) であるとは全単射 $\sigma\colon A\to\mathbb{N}$ で以下を満たすようなものが存在することである。
# $\sigma(i)=0$ である。
# 任意の $x\in A$ に対し $\sigma(f(x))=\mathrm{suc}(\sigma(x))$ である。

またPeanoシステム $\langle A,i,f\rangle$ が $\langle \mathbb{N},0,\mathrm{suc}\rangle$ に'''ほとんど同型''' (almost isomorphic) であるとは、任意の $x\in A$ に対して、ある $n\in\mathbb{N}$ が存在し、$a=f^n(x)$ が成り立つことである。

==== 定理（Simpson–横山[[CiteRef::SimpsonYokoyama13]]） ====
$\mathsf{RCA}^*_0$ 上で以下は同値である。
# $\mathsf{RCA}_0$ 。
# 任意の $\langle\mathbb{N},0,\mathrm{suc}\rangle$ にほとんど同型なPeanoシステムは $\langle\mathbb{N},0,\mathrm{suc}\rangle$ に同型である。
# 任意の無限集合 $C\subseteq \mathbb{N}$ に対し、単射 $f\colon\mathbb{N}\to C$ が存在する。
# 任意の無限集合 $C\subseteq \mathbb{N}$ 、任意の $n\in\mathbb{N}$ に対し $C$ の部分集合で濃度が $n$ となるものが存在する。

また$\mathsf{RCA}^*_0$ 上で以下は同値である。
# $\mathsf{WKL}^*_0$ 。
# 任意のPeano構造は $\langle\mathbb{N},0,\mathrm{suc}\rangle$ にほとんど同型である。

同様に $\mathsf{RCA}^*_0$ 上で以下は同値である。
# $\mathsf{WKL}_0$ 。
# 任意のPeano構造は $\langle\mathbb{N},0,\mathrm{suc}\rangle$ に同型である。


{{#referencelist:
|listtype=ul
|browselinks=false
|columns=2
|header=出典
}}

== 関連項目 ==
* [[順序数]]
* [[整数]]
* [[有理数]]
* [[p進数]]
* [[実数]]
* [[複素数]]
* [[四元数]]
* [[集合の基本的な用語、集合の演算]]

自然数

2021-03-03T15:19:59Z

そくらてす: Change to media wiki style

[[Category:数の集合|シゼンスウ]]
{{begin |preamble}}


{{newtheorem |type=theorem |display=定理}}
{{newtheorem |type=lemma |display=補題 |family=theorem }}
{{newtheorem |type=definition |display=定義 |family=theorem }}
{{newtheorem |type=prop |display=命題 |family=theorem }}
{{newtheorem |type=example |display=例 |family=theorem }}

<math>
\newcommand{\mathsetextension}[1]{%
\left\{ #1 \right\}%
}
\newcommand{\mathsetintension}[2]{%
\left\{ #1 \left| #2 \right.\right\}%
}
\newcommand{\mathof}[2]{%
\mathop{#1}\left(#2\right)%
}
\newcommand{\mathnat}{\mathbb{N}}
\newcommand{\mathreal}{\mathbb{R}}
\newcommand{\qed}{\blacksquare}
\newcommand{\mathrelbar}{\mathrel{|}}
</math>
{{end |preamble}}
'''自然数'''(natural number)とは、素朴には “ $0, 1, 2, \ldots$ ” のように数えられる「数」のことである。
現代数学においてはPeanoの公理を満たす構造として自然数全体の集合 $\mathbb{N}$ を定義し、
その元のことを自然数と呼ぶ。

== Peanoの公理 ==
この節では自然数全体の集合の定義である'''Peanoの公理'''について述べる。

{{theorem |type=definition |name=Peanoの公理 |label=def-Peano }}
空でない集合 $\mathbb{N}$ 、単射写像 $s\colon \mathbb{N} \to \mathbb{N}$ と $\mathbb{N}$ の元 $0$ が
次の1、2を満たすとき $\left(\mathbb{N}, \mathop{s}, 0 \right)$ を'''自然数全体の集合'''や
'''自然数の集合'''と呼ぶ:
# $0 \notin \mathof{s}{\mathbb{N}}$;
# 任意の$X \subseteq \mathbb{N}$ について、$0 \in X $ かつ $ \mathof{s}{X} \subseteq X$ ならば、$X=\mathbb{N}$。

$\mathbb{N}$ が自然数全体の集合であるとき、$\mathbb{N}$の元は'''自然数'''と呼ばれる。

== Peanoの公理を満たす具体例 ==
この節ではPeanoの公理を満たす例をみる。

{{theorem |type=example |name=集合系による |label=ex-N_with_set }}
以下のように帰納的に定義される最小の集合系 $\mathbf{N}$ はPeanoの公理を満たす構造と考えることができる。
# 空集合 $\emptyset$ は $\mathbf{N}$ の元である。
# $n \in \mathbf{N}$ であるとき, $n \cup \left\{ n \right\} \in \mathbf{N}$。

具体的には $\mathbb{N}=\mathbf{N}$, $0=\emptyset$, $\mathop{s}(n)=n \cup \mathsetextension{n}$ とすればよい。

{{theorem |type=example |name=記号列による |label=ex-N_with_symbols }}
記号の集合 $\mathsetextension{z, s}$ 上の記号列であって、
以下のように帰納的に定義される最小の記号列の集合 $\mathbf{N}$ は
Peanoの公理を満たす構造と考えることができる。
# 記号列 $z$ は $\mathbf{N}$ の元である。
# 記号列 $\mathbf{n}$ が $\mathbf{N}$ の元であるとき、文字列 $s\mathbf{n}$ は $\mathbf{N}$ の元である。

具体的には $\mathbb{N}=\mathbf{N}$, $0=z$, $\mathop{s}(\mathbf{n})=s\mathbf{n}$ とすればよい。

== 自然数全体の一意性 ==
自然数の集合は同型を除いて一意に定まる。

== $0$ は自然数か？ ==
自然数の集合の定義には $0$ を自然数に含む流儀と $0$ を自然数に含まない流儀がある。
この節ではそのことについて述べる。

=== Mathpediaでのスタンス ===
Mathpediaにおいては「$0$ を自然数とするかどうか」について、
各分野ごとの習慣やそれぞれで行っている議論における利便性に応じて、
適宜筆者の判断に委ねることとしている。
そのためこの記事以外のMathpediaの記事においては、
'''$0$ を自然数に含まない流儀が採用されることがある'''。
個別の記事を読む際には注意されたい。

==== $0$ を自然数に含まない流儀の場合のPeano の公理 ====
$0$ を自然数に含まない流儀の場合の自然数の集合は{{ref |type=definition |label=def-Peano }}の
$0$ をすべて $1$ に書き換えれば良い。

=== この記事でのスタンス ===

この記事においては、次の観点から $0$ を含む流儀を採用した。
* Peano の公理の具体例を構成する際、$0$ を含まない流儀を採用すると不自然になる
* 自然数の加法に単位元がほしい
* 集合論などでは $0$ を含む流儀が普通である

=== 落ち穂拾い ===
==== ISO 80000-2:2009 ====
数学記号について定義している国際規格であるISO 80000-2:2009 によると、

{| class="wikitable" style="margin: auto;"
! Item No.
! Sign, Symbol, expression
! Meaning, verbal equivalent
! Remarks and examples
|-
| 2-6.1
| $\mathbf{N}$
| the set of natural numbers, <br /> the set of positive integers and zero
|$\mathbf{N}=\mathsetextension{0, 1, 2, 3, \ldots}$ <br /> $\mathbf{N^{*}}=\mathsetextension{1, 2, 3, \ldots}$ <br /> Other restrictions can be indicate in an obvious way, as shown below. <br /> $\mathbf{N_{\lt 5}}=\mathsetintension{ n \in \mathbf{N} }{n \lt 5}$ <br /> The symbols $\mathrm{I\! N}$ and $\mathbb{N}$ are also used.
|}
と定義されている。日本語訳は以下のようになる。

{| class="wikitable" style="margin: auto;"
! 番号
! 記号、記号列
! 意味
! 注意および例
|-
| 2-6.1
| $\mathbf{N}$
| 自然数の集合、<br /> 正の整数およびゼロからなる集合
|$\mathbf{N}=\mathsetextension{0, 1, 2, 3, \ldots}$ <br /> $\mathbf{N^{*}}=\mathbf{N^{*}}=\mathsetextension{1, 2, 3, \ldots}$ <br /> 他の制限については以下のように表記できる。 <br /> $\mathbf{N_{\lt 5}}=\mathsetintension{ n \in \mathbf{N} }{n\lt 5}$ <br /> 記号$\mathrm{I\! N}$や$\mathbb{N}$もまた使われる。
|}

== Peano範疇性に対する逆数学 ==

Peanoシステムの範疇性定理については良く知られた事実であるが、この範疇性に対する逆数学として以下のような結果が知られている。

==== 定義（Peanoシステム） ====
$ A\subseteq\mathbb{N},i\in A,f\colon A\to A$ の組 $\langle A,i,f\rangle$ を'''システム''' (system) という。システム $\langle A,i,f\rangle$ が'''Peanoシステム''' (Peano system) であるとは、以下の条件を満たすことである。
# $i\notin\mathrm{rng}(f)$ である。
# $f$ は単射である。
# 任意の $X\subseteq A$ に対して、$i\in X$ かつ、任意の $x\in\mathbb{N}$ に対して $x\in X$ ならば $f(x)\in X$ であると仮定する。このとき $X=A$ である。

また $\langle \mathbb{N},0,\mathrm{suc}\rangle$ を標準的なPeanoシステムという。ここで $\mathrm{suc}(x):=x+1$ である。

==== 定義（同型） ====
Peanoシステム $\langle A,i,f\rangle$ が $\langle \mathbb{N},0,\mathrm{suc}\rangle$ に'''同型''' (isomorphic) であるとは全単射 $\sigma\colon A\to\mathbb{N}$ で以下を満たすようなものが存在することである。
# $\sigma(i)=0$ である。
# 任意の $x\in A$ に対し $\sigma(f(x))=\mathrm{suc}(\sigma(x))$ である。

またPeanoシステム $\langle A,i,f\rangle$ が $\langle \mathbb{N},0,\mathrm{suc}\rangle$ に'''ほとんど同型''' (almost isomorphic) であるとは、任意の $x\in A$ に対して、ある $n\in\mathbb{N}$ が存在し、$a=f^n(x)$ が成り立つことである。

==== 定理（Simpson–横山） ====
$\mathsf{RCA}^*_0$ 上で以下は同値である。
# $\mathsf{RCA}_0$ 。
# 任意の $\langle\mathbb{N},0,\mathrm{suc}\rangle$ にほとんど同型なPeanoシステムは $\langle\mathbb{N},0,\mathrm{suc}\rangle$ に同型である。
# 任意の無限集合 $C\subseteq \mathbb{N}$ に対し、単射 $f\colon\mathbb{N}\to C$ が存在する。
# 任意の無限集合 $C\subseteq \mathbb{N}$ 、任意の $n\in\mathbb{N}$ に対し $C$ の部分集合で濃度が $n$ となるものが存在する。

また$\mathsf{RCA}^*_0$ 上で以下は同値である。
# $\mathsf{WKL}^*_0$ 。
# 任意のPeano構造は $\langle\mathbb{N},0,\mathrm{suc}\rangle$ にほとんど同型である。

同様に $\mathsf{RCA}^*_0$ 上で以下は同値である。
# $\mathsf{WKL}_0$ 。
# 任意のPeano構造は $\langle\mathbb{N},0,\mathrm{suc}\rangle$ に同型である。

== 出典 ==
* Simpson, Stephen G., and Keita Yokoyama. "Reverse mathematics and Peano categoricity." Annals of Pure and Applied Logic 164.3 (2013): 284–293.

== 関連項目 ==
* [[順序数]]
* [[整数]]
* [[有理数]]
* [[p進数]]
* [[実数]]
* [[複素数]]
* [[四元数]]
* [[集合の基本的な用語、集合の演算]]

文脈自由言語

2021-03-02T03:42:29Z

そくらてす: /* 文脈自由言語の例 */ Fix a typo

[[Category:形式言語理論|ブンミャクジユウゲンゴ]]
{{begin |preamble}}


{{newtheorem |type=theorem |display=定理}}
{{newtheorem |type=lemma |display=補題 |family=theorem }}
{{newtheorem |type=definition |display=定義 |family=theorem }}
{{newtheorem |type=prop |display=命題 |family=theorem }}
{{newtheorem |type=example |display=例 |family=theorem }}

<math>
\newcommand{\mathsetextension}[1]{%
\left\{ #1 \right\}%
}
\newcommand{\mathsetintension}[2]{%
\left\{ #1 \left| #2 \right.\right\}%
}
\newcommand{\mathof}[2]{%
\mathop{#1}\left(#2\right)%
}
\newcommand{\mathderiv}{\mathrel{\mathop{\Rightarrow}^{*}}}
\newcommand{\mathgen}{\rightsquigarrow}
\newcommand{\mathgenfun}[1]{\mathbf{#1}}
\newcommand{\mirrorim}[1]{\overleftarrow{#1}}
\newcommand{\emptyword}{\varepsilon}
\newcommand{\kleenecl}[1]{{#1}^{*}}
\newcommand{\interpret}[1]{[\![#1]\!]}
\newcommand{\mathautomaton}[1]{\mathcal{#1}}
\newcommand{\mathnat}{\mathbb{N}}
\newcommand{\qed}{\blacksquare}
\newcommand{\mathrelbar}{\mathrel{|}}
</math>
{{end |preamble}}
'''文脈自由言語（context-free language）'''とは文脈自由文法によって生成される形式言語である。

文脈自由文法は句構造文法の一種であるから、
文脈自由言語は[[句構造言語]]の一種である。
また、文脈自由文法は文脈依存文法の一種であるから、
文脈自由言語は[[文脈依存言語]]の一種である。

以下、項目[[形式言語]]において定められている言語上の演算などについては特に断らず用いる。

== 文脈自由言語の導入 ==
この節では文脈自由言語を定義する。
<div>
{{theorem |type=definition |name=文脈自由文法 |label=def-context-free_grammar }}
'''文脈自由文法（context-free grammar）'''とは
# 記号集合 $\Sigma$
# $\Sigma$ と互いに素な'''変数記号（variable）'''の有限集合 $V$
# '''生成規則（production rule）'''と呼ばれる有限集合 $R \subseteq V \times \kleenecl{(\Sigma \cup V)}$
# '''開始記号(start symbol)'''または'''初期記号'''と呼ばれる $S\in V$

の４つ組$(V, \Sigma, R, S)$である。
</div>

<br>

これは、[[句構造言語#句構造文法 | 句構造文法]]の一種である。また、[[文脈依存言語#文脈依存文法 | 文脈依存文法]]の一種である。

[[句構造言語]]のときと同様、$\Sigma$ の元を'''終端記号(terminal)'''、$V$ の元を'''非終端記号(non-terminal)'''と呼ぶことも多い。

以下では、元$(A, \alpha)\in R$ のことを$A\mathgen\alpha$と書く。

[[句構造言語#def-derivation | 導出]]、[[句構造言語#def-phrase_structure_lang | 生成される言語]]などは
句構造言語と同様に定義される。

'''文脈自由言語'''とは何らかの文脈自由文法によって生成される言語のことを言う。

== 文脈自由言語の例 ==
この節では文脈自由言語の例を紹介する。

<div>
{{theorem |type=example |name=Dyck言語 |label=ex-Dyck_lang }}
$V=\left\{ S \right\}$,
$\Sigma=\left\{ [, ] \right\}$,
$R=\left\{ S\mathgen\varepsilon, S\mathgen [S]S \right\}$
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
この文脈自由文法によって生成される言語 $L(G)$ を'''Dyck言語'''と呼ぶ
</div>

Dyck言語の元となる記号列とその記号列を生成する導出の列をいくつかあげる。

<math>
\begin{gather*}
S \Rightarrow \varepsilon \\
S \Rightarrow [S]S \Rightarrow [\varepsilon]S \Rightarrow [\varepsilon]\varepsilon \equiv [] \\
S \Rightarrow [S]S \Rightarrow [[]]S \Rightarrow [[]]\varepsilon \equiv [[]] \\
S \Rightarrow [S]S \Rightarrow [\varepsilon]S \Rightarrow [\varepsilon][S]S \mathderiv [\varepsilon][\varepsilon]\varepsilon \equiv [][] \\
S \Rightarrow [S]S \Rightarrow [[S]S]S \Rightarrow [[[S]S]S]S \mathderiv [[[\varepsilon]\varepsilon]\varepsilon]\varepsilon \equiv [[[]]] \\
S \Rightarrow [S]S \Rightarrow [[S]S]S \Rightarrow [[S]S][S]S \mathderiv [[\varepsilon]\varepsilon][\varepsilon]\varepsilon \equiv [[]][] \\
S \Rightarrow [S]S \Rightarrow [S][S]S \Rightarrow [S][[S]S]S \mathderiv [\varepsilon][[\varepsilon]\varepsilon]\varepsilon \equiv [][[]] \\
S \Rightarrow [S]S \Rightarrow [S][S]S \Rightarrow [S][S][S]S \mathderiv [\varepsilon][\varepsilon][\varepsilon]\varepsilon \equiv [][][]
\end{gather*}
</math>

<div>
{{theorem |type=example |name=二進表現された自然数同士の四則演算の式全体 |label=ex-arithmetic_form_lang }}
<math>
\begin{align*}
V&=\left\{ S, B, B', M, P \right\}, \\
\Sigma&=\left\{ 0, 1, +, -, \times, \div, (, ) \right\}, \\
R&=\{ S \mathgen M, S \mathgen S + M, S \mathgen S - M, M \mathgen P, M \mathgen M \times P, M \mathgen M \div P, P \mathgen B, P \mathgen ( S ), B \mathgen 0, B \mathgen 1, B \mathgen 1B', B' \mathgen 0, B' \mathgen 1, B' \mathgen 0B', B' \mathgen 1B' \}
\end{align*}
</math>
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
この文法によって生成される言語は二進表現された自然数同士の四則演算の式全体である。
</div>

二進表現された自然数同士の四則演算の式の導出の例をあげる。

<math>
\begin{align*}
S &\Rightarrow M \\
&\Rightarrow M \div P \\
&\Rightarrow M \times P \div P \\
&\Rightarrow P \times P \div P \\
&\Rightarrow (S) \times P \div P \\
&\Rightarrow (S - M) \times P \div P \\
&\Rightarrow (S + M - M) \times P \div P \\
&\Rightarrow (M + M - M) \times P \div P \\
&\Rightarrow (P + M - M) \times P \div P \\
&\Rightarrow (B + M - M) \times P \div P \\
&\Rightarrow (0 + M - M) \times P \div P \\
&\Rightarrow (0 + P - M) \times P \div P \\
&\Rightarrow (0 + B - M) \times P \div P \\
&\Rightarrow (0 + 1B' - M) \times P \div P \\
&\Rightarrow (0 + 10 - M) \times P \div P \\
&\Rightarrow (0 + 10 - P) \times P \div P \\
&\Rightarrow (0 + 10 - B) \times P \div P \\
&\Rightarrow (0 + 10 - 1) \times P \div P \\
&\Rightarrow (0 + 10 - 1) \times B \div P \\
&\Rightarrow (0 + 10 - 1) \times 1B' \div P \\
&\Rightarrow (0 + 10 - 1) \times 10B' \div P \\
&\Rightarrow (0 + 10 - 1) \times 101 \div P \\
&\Rightarrow (0 + 10 - 1) \times 101 \div B \\
&\Rightarrow (0 + 10 - 1) \times 101 \div 1 \\
\end{align*}
</math>

<div>
{{theorem |type=example |name=(命題変数が有限の)命題論理の論理式全体 |label=ex-prop_form_lang }}
<math>
\begin{align*}
V&=\left\{ S \right\}, \\
\Sigma&=\left\{ p_1, \ldots p_n, \top, \bot, \lnot, \land, \lor, \to, (, )\right\}, \\
R&=\{ S\mathgen p_1, \ldots, S\mathgen p_n, S\mathgen \top, S\mathgen \bot,
S\mathgen(\lnot S), S\mathgen(S\land S), S\mathgen(S\lor S), S\mathgen({S\to S}) \}
\end{align*}
</math>

とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
</div>

この文脈自由文法によって生成される言語 $L(G)$ は[[数理論理学の基礎、命題論理]]において定義されている命題論理の論理式全体である（ただし、命題変数の集合の濃度を有限としたときに限る）。

<div>
{{theorem |type=example |name=$0^{n}1^{n}$ という形をした記号列全体 |label=ex-counter_example_reg_lang_n }}
$V=\left\{ S \right\}$,
$\Sigma=\left\{ 0, 1 \right\}$,
$R=\left\{ S\mathgen\emptyword, S\mathgen 0S1 \right\}$
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
この文脈自由文法によって生成される言語 $L(G)$ は $0^{n}1^{n}$ （ただし、$n\in\mathnat$）という形をした記号列全体になっている。
</div>

$0^{n}1^{n}$ という形をした記号列の導出の例をいくつかあげる。

<math>
\begin{gather*}
S \Rightarrow \varepsilon \\
S \Rightarrow 0S1 \Rightarrow 0\emptyword 1 \equiv 01 \\
S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 00\emptyword 11 \equiv 0011 \\
S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 000\emptyword 111 \equiv 000111 \\
S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 0000S1111 \Rightarrow 0000\emptyword 1111 \equiv 00001111 \\
S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 000S111 \Rightarrow 0000S1111 \Rightarrow 00000S11111 \Rightarrow 00000\emptyword 11111 \equiv 0000011111
\end{gather*}
</math>

<div>
{{theorem |type=example |name=$w\mirrorim{w}$ という形をした記号列全体 |label=ex-counter_example_reg_lang_mirror }}
$V=\left\{ S \right\}$,
$\Sigma=\left\{ 0, 1 \right\}$,
$R=\left\{ S\mathgen\emptyword, S\mathgen 0S0, S\mathgen 1S1 \right\}$
とすると、$G=(V, \Sigma, R, S)$ は文脈自由文法である。
この文脈自由文法によって生成される言語 $L(G)$ は $w\mirrorim{w}$ （ただし、$w\in \kleenecl{\Sigma}$）という形をした記号列全体になっている。
</div>

$w\mirrorim{w}$ という形をした記号列の導出の例をいくつかあげる。

<math>
\begin{gather*}
S \Rightarrow \varepsilon \\
S \Rightarrow 0S0 \Rightarrow 0\emptyword 0 \equiv 00 \\
S \Rightarrow 1S1 \Rightarrow 1\emptyword 1 \equiv 11 \\
S \Rightarrow 0S0 \Rightarrow 00S00 \Rightarrow 00\emptyword 00 \equiv 0000 \\
S \Rightarrow 0S0 \Rightarrow 01S10 \Rightarrow 01\emptyword 10 \equiv 0110 \\
S \Rightarrow 1S1 \Rightarrow 10S01 \Rightarrow 10\emptyword 01 \equiv 1001 \\
S \Rightarrow 1S1 \Rightarrow 11S11 \Rightarrow 11\emptyword 11 \equiv 1111
\end{gather*}
</math>

== BNF記法 ==
この節ではBNF記法について述べる。

<math>
\begin{align*}
V&=\left\{ S, A_{1}, \dots A_{n} \right\}, \\
R&=\{ S\mathgen \alpha_{00}, \dots S\mathgen \alpha_{0m_{0}}, \\
&\phantom{=\{} A_{1}\mathgen \alpha_{10}, \dots A_{1}\mathgen \alpha_{1m_{1}}, \\
&\phantom{=\{ A_{1}\mathgen \alpha_{10}, } \vdots \\
&\phantom{=\{} A_{n}\mathgen \alpha_{n0}, \dots A_{n}\mathgen \alpha_{nm_{n}} \}
\end{align*}
</math>

という、文脈自由文法 $G=(V, \Sigma, R, S)$ について、

<math>
\begin{align*}
S &::= \alpha_{00} \mathrelbar \dots \mathrelbar \alpha_{0m_{0}} \\
A_{1} &::= \alpha_{10} \mathrelbar \dots \mathrelbar \alpha_{1m_{1}} \\
\vdots \\
A_{n} &::= \alpha_{n0} \mathrelbar \dots \mathrelbar \alpha_{nm_{n}}
\end{align*}
</math>

という表記を $G$ の'''[[BNF記法]](Backus-Naur form)'''という。

この記法は、論理式の定義やプログラミング言語の定義などによく使われる。

=== BNFの例 ===
<div>
{{theorem |type=example |name=二進表現された自然数同士の四則演算の式全体 |label=ex-arithmetic_form_lang_BNF }}

[[文脈自由言語#ex-arithmetic_form_lang | 二進表現された自然数同士の四則演算の式全体]]を表すBNF記法は次のとおりである。

<math>
\begin{align*}
S &::= M \mathrelbar S + M \mathrelbar S - M \\
M &::= P \mathrelbar M \times P \mathrelbar M \div P \\
P &::= B \mathrelbar ( S ) \\
B &::= 0 \mathrelbar 1 \mathrelbar 1B' \\
B' &::= 0 \mathrelbar 1 \mathrelbar 0B'\mathrelbar 1B'
\end{align*}
</math>
</div>




== 参考文献 ==
# 新屋良磨、オートマトン理論再考、コンピュータソフトウェア、2017、34 巻、3 号、p. 3_3-3_35、公開日 2017/09/25、Print ISSN 0289-6540、https://doi.org/10.11309/jssst.34.3_3、https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja
# 五十嵐喜英他、『数理情報科学シリーズ２４オートマトンと形式言語の基礎』、牧野書店、2011

== 関連項目 ==
* [[形式言語]]
* [[BNF記法]]

{| class="wikitable" style="margin: auto;"
|+ Chomsky階層
! 文法のタイプ
! 言語のクラス
! 計算モデル
|-
! タイプ0
| [[句構造言語]]
| [[Turingマシン]]
|-
! タイプ1
| [[文脈依存言語]]
| [[線形有界オートマトン]]
|-
!タイプ2
| [[文脈自由言語]]
| [[プッシュダウン・オートマトン]]
|-
!タイプ3
| [[正規言語]]
| [[有限オートマトン]]
|}

Backus-Naur記法

2021-03-01T16:50:59Z

そくらてす: Fix a typo

[[Category:形式言語理論 |Backus-Naurキホウ]]
{{begin |preamble}}


{{newtheorem |type=theorem |display=定理}}
{{newtheorem |type=lemma |display=補題 |family=theorem }}
{{newtheorem |type=definition |display=定義 |family=theorem }}
{{newtheorem |type=prop |display=命題 |family=theorem }}
{{newtheorem |type=example |display=例 |family=theorem }}

<math>
\newcommand{\mathsetextension}[1]{%
\left\{ #1 \right\}%
}
\newcommand{\mathderiv}{\mathrel{\mathop{\Rightarrow}}^{*}}
\newcommand{\mathgen}{\rightsquigarrow}
\newcommand{\emptyword}{\varepsilon}
\newcommand{\kleenecl}[1]{{#1}^{*}}
\newcommand{\interpret}[1]{[\![#1]\!]}
\newcommand{\mathautomaton}[1]{\mathcal{#1}}
\newcommand{\mathnat}{\mathbb{N}}
\newcommand{\qed}{\blacksquare}
</math>
{{end |preamble}}
'''Backus-Naur記法'''(Backus-Naur form)
とは[[文脈自由言語]]の文法を定義するのに用いられる標準的な記法である。
BN記法、BNF記法や単にBNFとも呼ばれる。
通常，[[形式言語]]理論においては，記号集合を有限にするが，
この項目においては'''記号集合が無限であることがある'''。

以下ではBNF記法と書く。

== 概要 ==

形式的に厳密な定義については[[文脈自由言語#BNF]]を
参照のこと．

BNF記法にはさまざまなバリエーションがあるが共通して
\[\text{定義したい記号列を表すメタ記号}::=\text{記号列の並びを指定するメタ記号の列}\mathrel{|}\cdots\mathrel{|}\text{記号列の並びを指定するメタ記号の列}\]
という表現が用いられる。

たとえば、BNF記法を用いて自然数の二進表現 $B$ を表現すると次のようになる。
<nowiki>
\begin{align*}
{B} &::= {b\mathrel{|}1B'} \\
{B'} &::= {b\mathrel{|}bB'} \\
{b} &::= {0\mathrel{|}1}
\end{align*}
</nowiki>
この記法によって、$B$ は
\[0, 1, 10, 11, 100, 101, 110, 111, 1000,\ldots\]
という記号列全体を表現できている．

== BNF記法の具体例 ==
=== 命題論理の論理式の表現 ===
[[数理論理学の基礎1]]の記事に書いてある命題論理の論理式 $\varphi$ の定義は次のように表現できる。

<nowiki>
\begin{align*}
{p} &\in {\mathrm{PropVar}} \\
{\varphi} &::= {p \mathrel{|} \top \mathrel{|} \bot \mathrel{|} (\lnot\varphi) \mathrel{|} (\varphi\land\varphi) \mathrel{|} (\varphi\lor\varphi) \mathrel{|} (\varphi\to\varphi)}
\end{align*}
</nowiki>

=== 等式論理の項、論理式の表現 ===
[[数理論理学の基礎1]]の記事に書いてある等式論理の$\mathscr{L}$-項 $t$ と$\mathscr{L}$-論理式 $\varphi$ の定義は次のように表現できる。

\begin{align*}
{t} &::= {v\mathrel{|}f(\overbrace{t,\ldots,t}^{n\text{個}})} \\
{\varphi} &::= {t=t}
\end{align*}
ただし、$v$ は変数記号を表し、$f$ は項数 $n$ の関数記号である。

== 関連項目 ==
* [[形式言語]]
* [[文脈自由言語]]

{| class="wikitable" style="margin: auto;"
|+ Chomsky階層
! 文法のタイプ
! 言語のクラス
! 計算モデル
|-
! タイプ0
| [[句構造言語]]
| [[Turingマシン]]
|-
! タイプ1
| [[文脈依存言語]]
| [[線形有界オートマトン]]
|-
!タイプ2
| [[文脈自由言語]]
| [[プッシュダウン・オートマトン]]
|-
!タイプ3
| [[正規言語]]
| [[有限オートマトン]]
|}