形式言語・文法とは（全体像）
形式言語は、「正しい文字列の集まり」を、数学的にきっちり定義する考え方。人間の言葉（自然言語）はあいまいさを含むが、形式言語はあいまいさなく厳密に決めるのが特徴だ。
その中心になるのが文法。ここでの文法は「正しい文の見分け方」ではなく、「文字列を生み出すルール（生成規則）」のこと。ルールに従って記号を置き換えていくと、その言語の文字列ができあがる。
押さえる基本は次の4つ。
- 非終端記号 … まだ展開される途中の部品（記号）。
- 終端記号 … 実際に文字列に現れる文字。
- 開始記号 … 展開のスタート地点。
- 生成規則 … 「左を右に置き換える」というルール。
詳しく：文法の4要素と生成だけ覚えれば戦える
ここが記事の心臓部。まずは文法を作る4要素。
文法の4要素
| 要素 | 役割 |
|---|---|
| 非終端記号 | あとで展開される途中の部品（例：文・式） |
| 終端記号 | 実際に現れる文字（例：a、b、数字） |
| 開始記号 | 展開を始める記号 |
| 生成規則 | 「左 → 右」に置き換えるルール |
この4つで、文字列を生み出す（導出する）。たとえば「開始記号Sから、生成規則を何回か当てはめて、終端記号だけの文字列にする」のが導出だ。つまり、スタートの記号からルールを順に当てはめて文字列を作る、というわけだ。
生成規則の例（S → aSb ｜ 空）
| 適用 | できる文字列 |
|---|---|
| Sを空にする | （空） |
| 1回展開 | a b |
| 2回展開 | a a b b |
`S → aSb` は「Sを『a・S・b』に置き換える」というルール。これを繰り返すと、aとbが同じ数だけ並ぶ「ab」「aabb」「aaabbb」…が作れる。短いルールから無限の文字列を生み出せるのが文法の力だ。
なお、生成規則の形を制限すると、表現力の段階（チョムスキー階層）が決まる。文法の書き方の代表がBNF記法で、コンパイラの字句解析（記号化）・構文解析（構文木づくり）の土台になる。
わかりやすく言い換えると
要するに、形式言語は「あいまいさのない、機械が読める言葉」、文法は「その言葉の作り方レシピ」だ。
①終端記号 … 料理でいう「完成品に乗る具材」（実際に現れる文字）
②非終端記号 … 「下ごしらえ中の材料」（あとで展開される部品）
③生成規則 … 「材料をこう組み合わせる」という手順書
開始記号からレシピ（生成規則）どおりに展開していくと、その言語の文字列ができあがる。人間の言葉と違って、解釈のブレがないのがポイントだ。
試験のツボ
🔴 一番出る：文法の4要素
①非終端記号（途中の部品）・終端記号（実際の文字）
②開始記号（スタート）・生成規則（置き換えルール）
🔴 次に出る：生成（導出）のしくみ
①開始記号から生成規則を当てはめて文字列を作る
②短いルールから無限の文字列を生み出せる
🟡 押さえると安定：形式言語の特徴と応用
①形式言語はあいまいさなく厳密（自然言語と違う）
②BNFで記述し、コンパイラの字句・構文解析の土台
よくある間違い
①「形式言語は自然言語（日常の言葉）と同じものである」→ ✗ 形式言語はあいまいさのない、数学的に厳密な定義。自然言語とは別。
②「文法とは正しい文字列そのもののことである」→ ✗ 文法は文字列を生み出す「生成規則」。文字列そのものではない。
③「終端記号と非終端記号は同じもので、区別する必要はない」→ ✗ 終端は実際に現れる文字、非終端は展開途中の部品。役割が違う。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（文法の4要素）
形式言語の文法を作る要素に関する次の記述のうち、正しいものはどれか。
- 文法は非終端記号・終端記号・開始記号・生成規則の4つの要素から成り立つ
- 文法は終端記号だけからでき、非終端記号や生成規則は必要ないものである
- 文法は完成した正しい文字列の一覧表のことで、ルールは含まないものである
- 文法は1つの記号だけからでき、開始記号や生成規則は存在しないものである
解答は 1 だぜ。
文法は非終端記号・終端記号・開始記号・生成規則の4要素でできている。途中の部品（非終端）と実際の文字（終端）を、生成規則で組み立てるんだ。
選択肢2は「終端記号だけ」が誤り。選択肢3は「文字列の一覧表」が誤り（文法は生成規則）。選択肢4は「1つの記号だけ」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 非終端・終端・開始記号・生成規則の4要素 |
| 2 | ✗ | 非終端や生成規則も必要 |
| 3 | ✗ | 文法は生成規則であり一覧表ではない |
| 4 | ✗ | 複数の要素からなる |
オリジナル問題2（形式言語の特徴）
形式言語に関する次の記述のうち、正しいものはどれか。
- 形式言語は日常の自然言語と同じで、解釈にあいまいさが残るものである
- 形式言語は意味を持たない記号の羅列で、コンピュータでは扱えないものだ
- 形式言語はあいまいさなく厳密に定義され、コンパイラの理論の土台になる
- 形式言語は文字を1つしか持てず、複数の文字を並べることはできないものだ
解答は 3 だぜ。
形式言語はあいまいさなく厳密に定義され、コンパイラ理論（字句解析・構文解析）の土台になる。人間の言葉と違って、解釈のブレがないのが特徴だ。
選択肢1は「自然言語と同じ・あいまい」が誤り。選択肢2は「コンピュータで扱えない」が誤り。選択肢4は「文字を1つしか持てない」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | あいまいさがないのが特徴 |
| 2 | ✗ | コンパイラ理論で扱う |
| 3 | ✓ | 厳密に定義・コンパイラの土台 |
| 4 | ✗ | 複数の文字を並べられる |
オリジナル問題3（生成のしくみ）
生成規則 `S → aSb ｜ 空` で作れる文字列に関する次の記述のうち、正しいものはどれか。
- この規則ではaだけが何個も並び、bは一度も現れない文字列しか作れない
- この規則ではaとbが同じ数だけ並んだ「ab」「aabb」などが作れる
- この規則では文字列を作ることができず、生成は必ず途中で止まってしまう
- この規則ではaとbがばらばらの数で並び、規則性のない文字列だけができる
解答は 2 だぜ。
`S → aSb`は「Sをa・S・bに置き換える」ルール。繰り返すとaとbが同じ数だけ並ぶ「ab」「aabb」「aaabbb」…が作れる。短いルールから無限の文字列を生み出せるんだ。
選択肢1は「bが現れない」が誤り。選択肢3は「作れない」が誤り。選択肢4は「ばらばらの数」が誤りで、aとbは同数だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | bも同じ数だけ現れる |
| 2 | ✓ | aとbが同数の文字列が作れる |
| 3 | ✗ | 文字列を生成できる |
| 4 | ✗ | aとbは同じ数で並ぶ |
まとめ
押さえどころ
- 🔴 文法の4要素 ＝ 非終端記号・終端記号・開始記号・生成規則。
- 🔴 生成（導出） ＝ 開始記号から生成規則を当てはめて文字列を作る。短いルールから無限に生み出せる。
- 🟡 特徴と応用 ＝ あいまいさのない厳密な定義。BNFで記述し、コンパイラの字句・構文解析の土台。
次に学ぶ
- BNF記法・EBNF ── 文法（生成規則）を実際に書き表す記法。形式言語の理論が具体的な書き方になる。
- チョムスキー階層 ── 生成規則の形を制限すると決まる、言語の表現力の段階。形式言語の全体地図が見える。
執筆: SikakuQuest編集部