【けいしきげんご】
形式言語 とは？
最終更新:
💡 決めた記号で作る、文字列の集合
決めた記号から作る文字列の集合。文法やオートマトンでの記述、構文と意味の違い、文法の曖昧さを、短い文字列の例で解説します。
📌 このページのポイント
ひよこ 形式言語は、難しい言葉で話すこと？
ペンギン先生 ひよこ 無限にある文字列を、どうやって説明する？
ひよこ チョムスキー階層も、その分類？
ペンギン先生 生成文法などの能力に対応する言語のクラスだよ。正規言語、文脈自由言語、文脈依存言語、帰納的可算言語へと扱える範囲が広がる。個々の言語に難しさの順位を付ける話ではなく、どんな集合を表せるかという分類なんだ。
ひよこ 厳密に決めれば、曖昧さはなくなる？
ペンギン先生 必ずしもそうではない。一つの文字列に、異なる構文木を作れる文法は曖昧だ。たとえば演算の優先順位を定めない規則では、2+3*4を二通りにまとめる場合がある。文法が定義されていることと、解析結果が一意であることは別なんだ。
ひよこ コンパイラでは、何に役立つ？
もっと詳しく知りたい人へ
正規表現で、どんな入れ子も確認できる？
理論上の正規表現は、上限を決めない括弧の対応などを扱えません。有限の状態だけでは、開いた括弧の数を無制限に保持できないためです。ただし、実際の正規表現ライブラリには追加機能がある場合があるので、理論の正規表現と区別します。
文法と、言語は同じもの？
言語は文字列の集合、文法は文字列を生成する規則です。ある文法から生成できる文字列の集合を、その文法の言語と呼びます。同じ文字列集合を、異なる文法で表す場合もあります。構文木の曖昧さは、文法の側の性質としても確認します。
まとめ：ざっくりこれだけ覚えればOK！
「形式言語」って出てきたら「決めた記号から作る、文字列の集合」と思えばだいたいOK！
📖 おまけ：英語の意味
「Formal Language」 ＝ 形式言語
💬 Formalは、ここでは数学的な形で厳密に扱うことを表します。文法の曖昧さや文字列の意味が、自動で解決するという意味ではありません。