形式言語 とは？

日本語や英語のような「自然言語」はあいまいさがあるよね。「彼女は美しい花の絵を描いた」は複数の解釈ができる。形式言語は文法規則を数学的に厳密に定めて、あいまいさを完全に排除した言語のことだよ

言語学者のノーム・チョムスキーが提唱した分類で、文法の複雑さで言語を4段階に分けたものだよ。正規言語（Type 3）→ 文脈自由言語（Type 2）→ 文脈依存言語（Type 1）→ 帰納的可算言語（Type 0）の順に表現力が上がるんだ

プログラミング言語の構文はほぼ「文脈自由言語」として定義されているんだ。コンパイラは文脈自由文法のルールに従ってソースコードを解析する。BNF記法でプログラミング言語の文法を書くのは、まさに形式言語理論の応用だよ

正規言語は括弧の対応のようなネスト構造を扱えないけど、文脈自由言語は扱える。例えば「aをn個、bをn個」という言語は正規言語では表現できないけど、文脈自由言語なら可能なんだ。この違いがオートマトンの能力の差にも対応しているよ

パーサーやDSL（ドメイン固有言語）を設計するときに直結するよ。それに、正規表現の限界を理解していれば「HTMLを正規表現でパースしてはいけない理由」もすぐわかる。HTMLはネスト構造があるから文脈自由言語であって、正規言語では扱えないんだ。こういう判断ができるのが理論を学ぶ強みだね