regex - 正規表現は通常の文法用であり、____ は文脈自由文法用です

Question

Regular Grammarsに対応するFinite State Acceptorsものがあることを知りましたRegular Expressions。

と同等の変換はありContext Free Grammarsますか? 私が知る限り、文脈自由文法はPush Down Automata何に対応するもので表すことができますか?

これから私の心を片付けてくれる人に感謝します。

Answer 1

実際、答えはまだ「正規表現」である可能性があります。

最新の正規表現方言、特に再帰をサポートする方言 (PHP、Perl、.NET、JGSoft など)は、コンテキストフリー言語を完全に処理できます。

Answer 2

言語ではなく文法に言及しているという点で、質問の言い回しに問題があります。

正規言語は、和集合、連結、および閉鎖の操作を使用してセットに対して定義できる言語です。正規表現と正規文法はどちらも、正規言語を表す便利な方法です。

Context Free Languageの問題は、 Context Free Grammarによって受け入れられる言語として定義されているため、OP の質問に対する答えは言語カテゴリ定義自体の中にあるということです。