基本情報技術者試験(FE) ～情報の基礎理論「形式言語・数式記法」～【第1回】

情報の基礎理論

形式言語・数式記法その１

オートマトン

「オートマトン」とは、コンピュータの動作を数学的な観点からモデル化したもので、「入力」に対し、「状態」を変化させて処理を行い、「停止」することで結果を出力するといった、仮想的な機械の概念を示します。特に入力と状態の個数が有限個からなるオートマトンを「有限オートマトン」といいます。
「有限オートマトン」は、以下のような点を表または図で示します。

入力に対する状態変化を「状態遷移表」、「状態遷移図」で示す。
入力の開始位置は、初期状態（→で示す位置）から始まる。
入力に対する正常終了（これを「受理された」と呼ぶ）は、必ず受理状態で終わる必要があります。◎で示す。

次の図の「有限オートマトン」で、入力値として「10111」を入力した場合、「S0 → S1 → S0 　→ S1 → S3 → S2」と遷移するため、正常に受理されます。
一方、「11110」と入力した場合、「S0 → S1 → S3 → S2 → S4 → S4」と遷移するため、正常に受理されないことになります。

形式言語（正規表現）

私たちが日常的に使用する自然言語は、ある形式に従って言葉を作り、話す・記述することを行っていますが、その使用方法には多様性があり、形式を明確に定義することは困難です。
一方、コンピュータで使用する言語は、明確な定義のもとで作成した形式（フォーマット）に従い、文字やプログラムを読み、理解します。これを「形式言語」といいます。「形式言語」の代表的な表記として、「正規表現」、「BNF」などがあります。

「正規表現」は、文字列などの記号列を表現する形式言語です。「正規表現」では、有限個の記号に対して、規則を表す「メタ文字」を組み合わせて表現します。

メタ文字	意味
[A-Z]	英文字1文字を表す。
＊	直前の正規表現の0回以上の繰返し。
+	直前の正規表現の１回以上の繰返し。
?	直前の正規表現の0個または１個あることを表す。
｜	左右にある正規表現のいずれかを表す。