形式言語理論 01 – 形式言語とは | 情報科学のオデッセイ

今回から形式言語理論について解説をしていきたいと思います。とは言っても初めて学ぶ人は何のことかさっぱりだと思うので、第1回はその概要について説明していきます。

形式言語とは？

形式言語(formal language)は、アルファベット上の文字列の集合として定義されます。ここでいうアルファベットは有限の文字やシンボルの集合を指し、必ずしも日常でいうアルファベットの集合 ${A, B, C, \dots, Z}$ を指すわけではありません。例えば形式言語の分野では ${0, 1}$ という集合も、 $0$ と $1$ をそれぞれ文字として見れば、それらの集合はアルファベットといえるわけです。また明確に自然言語でないことがわかる文脈では単に言語と呼びます。

形式言語の例

例1

アルファベット ${a, b, c}$ 上の文字列として $ε$ , $a a a$ , $a b c$ , $a b a b$ , $a b c a b c a b c$ などがある。

$ε$ は空語と呼ばれる文字列で、文字列の長さが0であるものを指します。

要するに、アルファベット上の任意の組み合わせで作られる順序のついたシーケンスのことを文字列といっているんですね。

例2

アルファベット ${0, 1}$ 上の文字列の中で、その長さが4である言語は $0000$ , $0001$ , $0010$ , $0011$ , $0100$ , $0101$ , $0110$ , $0111$ , $1000$ , $1001$ , $1010$ , $1011$ , $1100$ , $1101$ , $1110$ , $1111$ の16種類である。

以下ではアルファベットの集合を $\sum$ と表します。例えばアルファベット ${0, 1}$ であれば、

$Σ = {0, 1}$

のように表します。ではもう少し複雑な条件を満たす言語を定義してみます。

例3

$Σ = {0, 1}$ 上で ${0^{n} 1^{n} | n ≧ 0, n \in Z}$ は $ε$ , $01$ , $0011$ , $000111$ などがある。

ここで定義される $n$ の条件は $0$ 以上の整数を意味しています。また $a^{n}$ は $a$ が $n$ 個連続して続く文字列を指します。

形式言語を考えることの意味について

形式言語が具体的にどういうものなのか少しだけ分かったと思いますが、果たしてこれってなんの役に立つの？？って思いますよね。では一旦、形式言語とは対をなす概念である自然言語について考えてみましょう。

自然言語について

自然言語とは我々人間が話す言語のことを指します。昔から人間は自身の感情や意図などを伝えるために言葉を使ってコミュニケーションを行ってきました。文法などの一定のルールはありますが、自然言語は例外があったり、文脈によって意味が変わってしまったり、時代によって文法の詳細が変わるケースもあります。つまり言語のルールの厳密性としては低いのです。

形式言語に戻ってみる

一方で、形式言語はどうでしょうか。形式言語は厳密なルールを定義することができます。例えば $Σ = {0, 1}$ において $0$ が偶数個含まれる文字列の集合は ${1, 00, 001, 010, 100, 0011, \dots}$ などのように無限に存在しますが、文字列 $01101101$ がこの集合に属さないことは $0$ の個数を数えればすぐに分かります。つまり形式言語は「形式性」、すなわち明確な規則に基づいて文字列がある文字列の集合(言語)に属するかどうかを判断できるということが特筆すべき性質なのです。

このように形式言語の性質や構造を数学的に研究する学問分野を形式言語理論と呼びます。具体的には「形式言語を定義する文法が生成・認識する言語の範囲や特性」を学んでいきます。

この理論は、コンピュータサイエンスにおける数多くの問題に応用されています。特にプログラムの構文解析、正規表現を使用したテキストのマッチング、コンパイラの設計、通信プロトコルの安全性確認などです。また、形式言語理論は計算理論の一部として、計算の可能性や限界についての理解を深める助けともなります。

まとめ

形式言語はアルファベット上の文字列の集合として定義される。
自然言語と比較して形式言語は明確な規則を定めることができる。
形式言語理論はコンピュータサイエンスの多くの問題に応用されている。