曖昧な文法(あいまいなぶんぽう、〈直訳すると「多義的な文法」〉)とは、構文木が唯一にならないかもしれない文法のことである。ここでは、自然言語は文法自体が不確かであることが多いため、そうではない形式言語に議論を限定するが、自然言語にも同様なことを考えることは可能である。形式言語的な文法を持つ言語が「本質的に曖昧である」とは、その言語を生成できるような文法は曖昧な文法にならざるをえないということである。例.次の文脈自由文法、なお、この規則から生成される言語は、記号列の集合としての言語としては、「本質的に曖昧」ではない。次のような曖昧さの起きない規則で、同じ記号列の集合を生成できるからである。プログラミング言語.曖昧な文法の認識.任意の文法についてそれが曖昧かどうかという問題を一般に判定する方法は無い。すなわちそのアルゴリズムは存在しない(もし存在するとすれば、停止性問題が判定できてしまう)。プログラミング言語など、形式言語の構文解析で使われる構文解析器では、解析結果が唯一であることを前提としていることが多い。多義性を扱うこと自体は、構文解析が失敗した場合だけでなく、成功した場合も他にも解析が可能ではないかを探すバックトラックを行えばよいだけである。それ自体よりも、多義的な箇所が複数ある場合に組合せ爆発になるので、それを全て列挙するといったような非現実的な処理を回避し、効率よく多義性を表現するにはどうしたらよいか、というような点は問題となる。パーサジェネレータ.実用性を重視したパーサジェネレータでは、中置記法の数式のような文法について、生成規則だけでは曖昧になるような規則で書くことを許し、それを補助するような、演算子について優先順位や結合性()を示す規則を追加することで曖昧さを解決する、というような手法が提供されている。本質的に曖昧な言語.対関数対関数は非可算無限個存在する。したがってその中には計算可能関数でないものが非可算無限個存在する。計算可能性理論や計算複雑性理論の文脈では、ある複雑性クラスの中で対をコード化して扱いたいことがあることから、対関数とその逆関数がともに目的の関数クラスに属するような符号化を見つけることが重要となる。定義.対関数は次のような全単射関数である。カントールの対関数.