形式言語

形式言語は、ふだんの生活でなじみのある「言語」という概念を一般化したものです。

基本用語

まずは、形式言語を日本語のようなふつうの言語として思いうかべてみましょう。言語は何からできているでしょうか。言語は語からできていて、語をつなげて文をつくります。ここでは文は考えず、語だけを考えます。では、語は何からできているでしょうか。アルファベットの文字からです。そこで、まずアルファベットを考えます。

アルファベットとは、空でない任意の集合のことです。アルファベットの要素を記号といいます。日本語なら、ひらがな、カタカナ、漢字などの文字全体がアルファベットになります。日本語ではなく、例えば数を表したいなら、アルファベットには10個の数字すべてを入れます。アルファベットはよく記号 Σ で表します。

語（文字列）とは、あるアルファベット Σ の記号を有限個並べた列のことです。例えば、アルファベット Σ= {a,b,c,d,e,…, z} があるとき、「sakura」や「neko」という列は語です。しかし、「kōen」（文字「ō」がない）、「Tokyo」（文字「T」がない）、「konnichi wa」（空白がない）は語ではありません。語を構成する記号の個数を、語の長さといいます。

語の連接： 2つの語 a = a₁a₂… a_n と b = b₁b₂… b_m があるとき、語を連接すると語 ab = a₁a₂… a_nb₁b₂… b_m ができます。例えば、語「sakura」と「neko」を連接すると、語「sakuraneko」ができます。連接は丸を使って a ∘ b と書くか、何も記号を書かずに語をそのまま続けて書きます。

空語は ε で表し、長さが0の語のことです。語 a = a₁… a_n に空語 ε を連接すると、もとの語 a が得られます。つまり、a ∘ ε = a が成り立ちます。

アルファベット Σ のクリーネ閉包とは、アルファベット Σ からつくることのできるすべての語の集合で、空語も含みます。クリーネ閉包は Σ^∗ で表します。2文字のアルファベット Σ= {0, 1} については、次が成り立ちます。

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

アルファベットの正閉包を使うこともあります。これも、アルファベットからつくることのできるすべての語の集合ですが、空語だけは含みません。正閉包は Σ⁺ で表し、Σ⁺ = Σ^∗ ∖ {ε} が成り立ちます。

アルファベットの例

• 日本語の例にもどりましょう。日本語の語はどれも、ひらがな、カタカナ、漢字（それに長音符「ー」など）を含むアルファベットのクリーネ閉包の中にあります。このアルファベットに句読点などの記号（読点、句点、感嘆符、疑問符など）を加えると、そのクリーネ閉包には日本語でつくれるすべての文が含まれます。もちろん、このクリーネ閉包には「ぬぬふぬ、あほへらぺ、ぽぴゅぎゃろ！！！？？？」のような文も含まれます。

• アルファベットがすべての数字 Σ= {0, 1, …, 9} からなるとき、そのクリーネ閉包にはすべての自然数が含まれ、さらにそれ以外のものも含まれます。例えば00054のように0から始まる数や、0そのもの、それに空語も含まれます。空語はもちろん数ではありません。

• アルファベットは空であってはいけないので、いちばん小さいアルファベットでも記号を1つはもちます。例えば、アルファベット Σ= {!} のクリーネ閉包は Σ^∗ = {ε, !, !!, !!!, !!!!, …} です。これは語の集合で、0以上の整数 n ∈ ℕ₀ のそれぞれについて、感嘆符を n 個並べた語がクリーネ閉包の中にあり、それ以外の語はありません。

• Σ= {qw,c} とします。これはとても変わったアルファベットで、語 qw を含んでいます。わかりにくくて不自然なので、ふつうこのような書き方はしませんが、文字「q」と「w」をくっつけて1つの文字にしたと考えることができます。すると、語「qw」を記号「qw」とみなせます。この記号を使って語「qwcqw」をつくると、この語の長さは3です。記号「qw」、「c」、「qw」からできているからです。このようなアルファベットにはあまり出会いませんが、複数の記号からなる記号を使う必要がある場面もあります。

形式言語

アルファベット Σ 上の（形式）言語とは、Σ^∗ の任意の部分集合のことです。したがって、アルファベット Σ 上の言語 L については、L ⊆ Σ^∗ が成り立ちます。言語の例を見てみましょう。

• 前の節で、数字のアルファベット Σ= {0, 1, …, 9} を定めました。そのクリーネ閉包は、数字だけからなるすべての語です。ここに「語は0から始まってはいけない」「語は空であってはいけない」という規則を加えると、自然数の集合 ℕ が得られます。ℕ ⊆ Σ^∗ が成り立つので、ℕ はアルファベット Σ 上の言語です。

• 上の数字の集合に、マイナスの記号「-」を加えて Σ= {0, 1, …, 9, −} とすることもできます。クリーネ閉包は、数字とマイナスの記号からなるすべての語です。ただし、そうするとクリーネ閉包には「12-84-」、「1-5-8」、「-」のような語も含まれます。整数の集合 ℤ の言語は、次の3つの規則を加えてつくります。

  • マイナスの記号は、語にまったく現れないか、語のはじめに現れる。
  • 語「0」を除いて、語の最初の数字は0であってはいけない。
  • どの語も少なくとも1つは数字を含む。

  この集合は整数の集合を表していて、集合 Σ^∗ の部分集合です。つまり、アルファベット Σ 上の言語です。

• Σ= {0, 1} とします。そのクリーネ閉包は、0と1からなるすべての語です。このアルファベット上の言語 L は、例えば「1をちょうど3個含むすべての語の集合」として定められます。もっと自由に、言語 L を「正しい docx 形式（ワープロソフトで保存する文書ファイル）を表すすべての語の集合」とすることもできます。

• 引き続き、2文字のアルファベット Σ= {0, 1} を考えます。どんな文字列（キーボードにあるふつうの文字の列）も、例えば ASCII コード表を使えば2進数の形、つまり0と1の列に変換でき、逆にもどすこともできます（正確にいうと、ASCII コード表は文字を数に変換し、10進法の数は2進法の数に変換できます）。そのため、有効なメールアドレスを表すすべての語の言語を定めることもでき、それもやはり2文字のアルファベット上の言語になります。

言語の連接： 言語どうしも連接できます。定義は集合の直積と似ています。2つの言語 L₁ と L₂ を考えます。その連接 L₁ ∘ L₂ は、次のように定める新しい言語です。

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

つまり、言語 L₁ のすべての語を、言語 L₂ のすべての語と連接します。例を見てみましょう。次の2つの言語を考えます。

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,neko\}\end{array}$$

このとき、次が成り立ちます。

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0neko,1a,1b,1neko\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,neko0,neko1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

ここまでは、言語を表すのにふつうの言葉を使ってきました。つまり、言語がどのようなものかを言葉で説明してきました。しかし、これはとても不便なので、言語を定めるもっと形式的な方法が導入されています。その1つ目が文法です。