日本語の文は、多少くずれていても通じます。 けれどもプログラム言語は、書き方の規則にあてはまらない文をすべて拒否します。 この回で扱うのは4つです。「すべて」「ある」を含む文を扱う述語論理、 文法の規則を書く記法である BNF、その規則にあてはまるかを判定するオートマトン、 そしてかっこを使わずに計算の順番を表す逆ポーランド表記。 どれも、あいまいさを残さずに言葉や式を扱うための道具です。
出典：基本情報技術者試験 シラバス Ver9.2 大分類1 基礎理論／中分類1 基礎理論／3. 情報に関する理論
（4）述語論理
述語論理の基本的な考え方，演繹推論と帰納推論の違いを理解する。
（5）形式言語
形式言語とは何か，言語の定義，演算，種類，文法を理解する。また，BNF，構文図式などの表記法，正規表現，文脈自由文法のあらましを理解する。
（6）オートマトン
有限オートマトンの概念，形式言語との関係，状態遷移表，状態遷移図を理解する。
述語論理 ── 「すべての」と「ある」を扱う
1-4 で扱った命題論理は、「雨が降っている」のような文をまるごと1つの真偽として扱いました。 これだと「すべての学生は学生証を持つ」のような文が書けません。文の中に変数が要るからです。
そこで、文を主語にあたる部分と、それについて述べる部分に分けます。 「x は学生である」のように書いて、x に何を入れても真偽が決まる形にしたものを述語といい、 これを扱う論理が述語論理です。ここに「すべての x について」「ある x について」を付けて、文を組み立てます。
「すべての学生は学生証を持つ」を組み立てる
すべての x について（x は学生である ならば x は学生証を持つ）
ある x について（x は学生である かつ x は学生証を持たない）
下の文は、上の文の否定です。「すべてが正しい」を崩すには反例が1つあればよい、という関係が、 そのまま「すべての」と「ある」の入れ替えになっています。 条件にあてはまる行をすべて取り出す関係データベースの問い合わせも、この考え方の上に立っています（第9章で扱います）。
述語論理は、規則から結論を導くための道具でもあります。その導き方には、向きの違う2種類があります。
先に、ひとつ予想してみましょう
「これまで観測したカラスは、すべて黒かった。だから、カラスは黒い」。 この進め方の名前はどれですか。
2つの推論
演繹推論 … 一般の規則から個別の結論を出す。前提が正しければ、結論も必ず正しい
帰納推論 … 個別の観察から一般の規則を作る。反例が1つ出れば崩れる
演繹は前提さえ正しければ確実、帰納は「たぶん正しい」止まりです。 データを集めて規則を作る機械学習（1-9）は、帰納推論の側にあります。 だから、学習に使わなかったデータで外れることがあり、検証が必要になります。
形式言語と BNF ── 文法を規則で書く
あいまいさが残らないよう、規則によってきちんと定めた言語を形式言語といいます。 プログラム言語の文法はこれです。その文法を書き表す記法の代表が BNF（バッカス・ナウア記法）です。
整数を定義する規則 <数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <整数> ::= <数字> | <整数><数字> ::= 左を右のように定める | または < > これから中身が決まるもの（非終端記号）
2行目は、自分自身（<整数>）を定義の中に使っています。これで「数字をいくつでも続けられる」ことを、たった1行で表せます（この規則では、最低でも1個は必要です）。
ある文字列がこの規則で作れるかどうかは、規則にしたがって書き換えていけるかで決まります。
この規則で 305 が作れるかを、1手ずつたどる
<整数>
→ <整数><数字>（2つ目の書き方を選ぶ）
→ <整数><数字><数字>（左の <整数> にもう一度）
→ <数字><数字><数字>（左の <整数> を1つ目の書き方に）
→ 3<数字><数字>（ここから数字を入れていく）
→ 30<数字>
→ 305（< > が残らず、目的の 305 になった＝作れる）
このように書き換えていくことを導出といいます。< > をすべて消し終えたときに目的の文字列そのものになれば、その文字列はこの規則で作れます。
試験で問われるのは、たいてい「この規則では作れない文字列はどれか」です。 どの書き方を選んで書き換えても、その文字列に行き着かないものが答えになります。
練習
次の規則があります（<数字> は上の 0〜9 と同じです）。
<英字> ::= A | B | C | … | Z
<識別子> ::= <英字> | <識別子><英字> | <識別子><数字>
このとき、作れない文字列はどれですか。
BNF のまわりで出てくる言葉
構文図式 … BNF と同じ内容を、線と矢印の図で表したもの。人が読みやすい
正規表現 … 文字の並びのパターンを1行で表す記法。たとえば 0*10* は「1 がちょうど1個」を表す（* は直前の文字の0回以上のくり返し）
文脈自由文法 … BNF で書き表せる文法の種類。かっこの対応のような入れ子を表せる
逆ポーランド表記 ── 演算子を後ろに書く
ふだん書く A + B のように、演算子を2つの値のあいだに置く書き方を中置記法といいます。 これに対して、演算子を後ろに置く A B + の書き方が逆ポーランド表記法（後置記法）です。
(A + B) × (C − D) を逆ポーランド表記にする
まず A + B を、演算子を後ろに回して「A B +」にする
次に C − D を、同じように「C D −」にする
最後に、この2つを掛ける。掛ける記号も後ろに回して
A B + C D − ×
かっこが1つも要らなくなりました。書く順番そのものが計算の順番になっているからです。
計算するときは、左から1つずつ読んで、数はいったん置いておきます。
7 3 − 2 × を左から1つずつ読む 7 と 3 を置く。置き場は「7 3」 − が来たので、先に置いた 7 から 3 を引く。7 − 3 ＝ 4。置き場は「4」 2 を置く。置き場は「4 2」 × が来たので、4 × 2 ＝ 8。置き場は「8」
演算子が来たら、直前に置いた2つを取り出して計算し、結果を置き直します。引き算と割り算は先に置いたほうが左側です（置き場が 7 3 なら 7 − 3 であって、3 − 7 ではありません）。
かっこも優先順位の規則も要らないので、コンピュータはこの形のほうが扱いやすいのです。 中置記法に戻すときは逆で、演算子が来るたびに直前の2つをかっこでくくり直していきます。
練習
2 3 4 × + を計算すると、いくつになりますか。
オートマトン ── 読んだ文字で場所が移る
ある文字列が規則にあてはまるかを判定する側の仕組みがオートマトンです。 状態がいくつかあって、文字を1つ読むごとに次の状態へ移ります。 状態の数が有限のものを有限オートマトンといいます。
1 の個数が偶数のときだけ受け付ける仕組み（状態遷移図）
0 0
+-+ +-+
| v | v
--> ((S0)) ------ 1 ------> ( S1 )
^ |
+---------- 1 ----------+
((S0)) 受理状態（かっこが二重になっている）
--> 開始の状態を指す印
1 1 を読んだとき。上は S0 から S1 へ、下は S1 から S0 へ
0 0 を読んだとき。自分の状態に戻る（自己ループ）
状態は S0 と S1 の2つだけです。1 を読むたびに反対側へ移り、0 では動きません。つまり S0 にいる＝これまでに読んだ 1 が偶数個、という意味になります。
同じ内容を表にしたもの（状態遷移表）
| 0 | 1
------+----+----
S0 * | S0 | S1
S1 | S1 | S0
* ＝ 受理状態
左の列が「いまの状態」、上の行が「読んだ文字」で、交わったところが移った先です。図と表は同じ内容を表しています。
入力を最後まで読んだとき、受理状態にいれば受け付ける、そうでなければ受け付けないと判定します。
入力 1011 をたどる 開始は S0 1 を読む → S1 0 を読む → S1（0 では移らない） 1 を読む → S0 1 を読む → S1 受理状態ではないので、受け付けない
1011 に含まれる 1 は3個。奇数なので、たどり着いた先は受理状態ではありません。
正規表現で書けるパターンは、必ず有限オートマトンで判定できます。 先ほどの 0*10* も、状態を並べれば同じように判定できます。 ただし、かっこの対応のように「どこまで開いたか」を覚えておく必要があるものは、 状態の数が有限では足りません。そこは文脈自由文法（BNF）の担当になります。
試験では、図ではなく表だけが与えられることがあります。表からたどってみましょう。
別の仕組み（状態遷移表だけが与えられた場合）
| a | b
------+----+----
P | Q | P
Q | Q | R
R * | Q | P
* ＝ 受理状態、開始は P
こんどは読む文字が a と b で、受理状態は R です。開始の P から表のとおりにたどって、最後に R にいれば受け付けます。
練習
上の表の仕組みに、次の入力を与えます。 受け付けられるのはどれですか。
まとめ
この回で持ち帰ること
1. 述語論理は「すべての x について」「ある x について」で文を組み立てる。否定すると、この2つは入れ替わる
2. 演繹推論は一般から個別で、前提が正しければ結論も必ず正しい。帰納推論は個別から一般で、反例に弱い
3. BNF は ::= で定め、| が「または」。自分自身を使って、いくつでも続く形を表す
4. 作れるかどうかは、< > を消し終えたときに目的の文字列そのものになるかで決まる
5. 逆ポーランド表記は演算子が後ろ。演算子が来たら直前の2つを計算する
6. オートマトンは、最後まで読んだときに受理状態にいるかで判定する
次に読む
この記事で引用した資料
いずれも独立行政法人情報処理推進機構（IPA）が公表したものです。IPAは公表済みの試験問題について、教育目的での使用に許諾および使用料を不要としていますが、著作権は放棄していません。本記事では問題文を改変せずに引用しています。
本文の例（整数と識別子の BNF、逆ポーランド表記の式、2つのオートマトン）と練習問題は、すべて当サイトが説明のために作ったものです。
