まずは形式言語というものを簡単に紹介し、いくつかの応用例を見ます。
形式言語とは文字列の集合のことです。例えば、「コンピュータ」という文字列を含む文字列全体の集合 \(S\) や、「山」と「川」を同じ回数含む文字列全体の集合 \(T\) は形式言語です。「コンピュータフリーク」は \(S\) の要素ですが、「海千山千」は \(T\) の要素ではありません。文字列と形式言語が与えられると、その文字列がその形式言語に含まれるかどうかは一意に決まります。
形式言語の対義語は自然言語です。これは、日本語や英語など自然発生した言語のことを指します。「私は学生です」は日本語の文字列ですが、「学生はが私すで」は日本語かどうかあやしいです。漢字とひらがなで構成されている点でいえば日本語のようですが、正しい文にはなっていません。これが日本語かと聞かれたら違うと答える人もれいば、そうだと答える人もいるでしょう。尋ねる人を問わず「コンピュータフリーク」が \(S\) に入ることが明らかだったこととは対照的です。
このように、ある文字列がその言語の要素かどうかが一意に定まることが形式言語の重要な特徴です。
形式言語を学ぶことがどのように役立つかを二つの例を用いて考えます。
検索エンジンやメールボックスから文書を検索するのは現代人であれば日常的に行っている行為です。たとえば「コンピュータ」という単語を含む文書をメールボックスから取り出したいとしましょう。メールアプリに「コンピュータ」と打ち込んで検索すれば結果が出てきます。ワイルドカードをサポートするアプリであれば「*コンピュータ*」という検索ワードでもよいでしょう。
これは形式的にいうと、「コンピュータ」という文字列を含む文字列全体の集合 \(S\) とメールボックスに含まれる文書の集合の共通部分を取り出す操作になります。
「コンピュータ」という単語を含む文書を見つけるくらいであればわざわざ形式的に述べる意味はありません。しかし、「山」と「川」を同じ回数含むメールを取り出したければどうでしょう？何と検索すれば絞り込めるでしょうか。「山 川」で検索しても「山川川」というように「山」が一回に対して「川」が二回登場するものまで引っかかってしまうかもしれません。
正規表現はワイルドカードを一般化した表記法です。プログラミング上でもよく使われるので聞いたことがある方もいるかもしれません。正規表現により表現できる人工言語を正規言語といいます。実は、「山」と「川」を同じ回数含む言語は正規言語でないのです。つまり、単語検索やワイルドカードだけをサポートしている検索エンジンには、「山」と「川」を同じ回数含むメールを取り出すという操作はできないのです。
形式言語理論では、正規表現で表現できる言語はどのようなものか、そしてどうすれば正規表現やワイルドカードを使って検索できるかを学びます。そして、逆にどのような言語が表現できないかについても学びます。「山」と「川」を同じ回数含む言語はその一例です。これらを学ぶことで、検索方法の幅が広がるだけでなく、逆に正規表現では十分でないことが分かったとき、より高度な検索エンジンを使う必要性にも気づけます。
プログラミング言語も形式言語です。あるプログラムが「正しい」プログラムであるかどうかは一意に決まり、正しくなければコンパイラがエラーを出して教えてくれます。
プログラミング言語とコンパイラを自分で作るとしましょう。（コンピュータサイエンスの学生にとって、プログラミング言語やコンパイラは使うだけでなく、自分で作るものでもあります！）コンパイラはプログラムを受け取ったときに、そのプログラムが正しいかどうかを検証し、間違っていたらエラー箇所を出力しなければなりません。
形式言語理論では、言語の定義の仕方や、ある文字列が言語に含まれるかどうかを判定する方法も学びます。これにより、自分でプログラミング言語を設計して、正しさを検証するプログラムを書くことができるようになります。
- 形式言語とは文字列の集合のこと
- 自然言語と違い、ある文字列が形式言語に含まれているかどうかは一意に定まる
- 形式言語理論は文書検索やプログラミング言語の基礎になっている
