私たちが日常会話で使用する自然発生した言語自然言語に対して、数学的に定義された単語の集合のことを形式言語といます。例えばプログラミング言語も形式言語、データベースからバナナという言葉が含まれる文章を全て取ってきたいとき、「バナナが含まれるすべての文字列」という集合も形式言語になります。形式言語理論では形式言語を表現する方法学び、形式言語の種類によっては表現する難しさが異なることを学びます。例えばあるプログラムがその言語の文法に従っているかをチェックするのに形式言語理論の技法が使えます。
形式言語を認識する単純なコンピューターのことをオートマトンといいます。オートマトンは文字列を受け取ると、その文字列が言語に含まれるかどうか判定します。形式言語理論では、様々な種類のオートマトン学び、それぞれの種類は認識できる言語が異なることを学びます。有限オートマトンとプッシュダウンオートマトンはその一例です。有限オートマトンは正規言語と呼ばれる種類の形式言語を認識できます。正規言語は「バナナが含まれるすべての文字列」のような非常に単純な形式言語です。プッシュダウンオートマトンは文脈自由言語という種類の形式言語を認識できます。これはプログラミング言語など、正規言語よりも更に広い範囲の言語まで含まれるクラスです。
前述のように、有限オートマトンで認識できる言語のこと正規言語といいます。これは正規表現と呼ばれる表現方法で表現できる言語と同じです。正規表現は私たちが検索エンジンで文章を検索するときやデータベースから欲しいテキストを検索するときなどに使われます。形式言語理論は非常に基礎的な理論的な学問ですが、正規表現のようにエンジニアリングとも密接に結びついている分野です。
数学的に定義された単語の集合を認識言語といいます。形式言語理論ではそのような言語がどのような方法で表現されるかを学びます。
