私はちょうどプログラミング言語の原則を通り抜けていました。正規文法と文脈自由文法の概念とその使い方を知っています。しかし、どちらがより強力で、その理由はまだわかりません。助けてください
前もって感謝します。
1 に答える
3
すべての正規言語は文脈自由ですが、一部の文脈自由言語は規則的ではありません。その意味で、文脈自由言語は通常の言語よりも「強力」です。
文脈に依存しない非正規言語の一例として、文字 x と y で構成されるすべての回文の言語を考えてみましょう。この言語が非正則であることは、ポンピング補題または Myhill-Nerode の定理を使用して証明できます。ただし、文法によって生成されるため、文脈自由です。
S→aSa | bSb | | | b | ε
直観的に、通常の言語は、限られたメモリを持つコンピューターで解決できるイエス/ノーの質問に対応します (Myhill-Nerode の定理は、この直感を形式化する 1 つの方法です)。これは、限られたメモリだけでは解決できないイエス/ノーの問題は、通常の言語に対応しないことを意味します。コンテキストフリー言語は、奇妙な中間点を占めています。それらは、有限のメモリと無制限のスタックを備えたコンピューターで解決できる問題に対応しています。
これについて詳しく知りたい場合は、形式言語と計算可能性に関する本を一読することをお勧めします。これらのクラスの言語については驚くほど美しい結果がたくさんありますが、それを 1 つの答えに圧縮することはできません。
お役に立てれば！
于 2014-09-10T01:08:41.987 に答える