computer-science - 言語が文脈自由かどうかを判断するにはどうすればよいですか?

Question

言語が文脈自由かどうかはどうすればわかりますか?

Answer 1

まず、主題の言語を形成する文脈自由文法の構築を試みる必要があります。すべてのプロダクションの左側に非終端記号が1つだけ含まれている場合、文法は文脈自由です。定義上、存在する場合、その言語は文脈自由です。

同等の構成は、プッシュダウンオートマトンです。DFAと同じですが、スタックが利用可能です。文法よりも構築する方が簡単かもしれません。

ただし、文法やオートマトンの作成に失敗した場合でも、言語が文脈自由ではないという意味ではありません。おそらく、トリッキーな文法を作成できないのはあなただけです（たとえば、トリッキーな言語の文法を作成するのに約7時間費やしたことがあります）。

言語が文脈自由であるかどうか疑問に思い始めた場合は、いわゆる「文脈自由言語のポンピング補題」を使用する必要があります。それはすべての文脈自由言語の特性を説明しており、あなたの言語がそれに違反している場合、それは間違いなく文脈自由ではありません（ウィキペディアの使用上の注意を参照してください）。

この補題は、オグデンの補題の結果です。したがって、Ogdenはより強力であり、反復補題を適用できなかった場合は、Ogdenを試すことができます（同じように使用されます）。

Answer 2

編集

言語が非CFGであることを証明するためのコメントで示唆されているように、私はオグデンの補題を使用することによると信じています。私の以前の答えに含まれている固有の誤解は許されるべきです:)潜伏者のために以前の答えを保持します。

古い答え

使用されている文法とルールを見てください！画像からわかるように（提供：ウィキペディアのチョムスキー階層）。正規言語のみが文脈自由ではありません。A->aBまたはA->Baの形式のものだけを使用するものを暗示することは、文脈自由ではありません。

編集 A->aBおよびA->Baの定義は、左および右の再帰文法を表現するためのものであり、文字通りに解釈されるべきではありません。

Answer 3

言語が文脈自由かどうかを判断するには、その言語の文法が必要です。すべての生成が「（非終端記号）->終端記号と非終端記号のシーケンス」の形式である場合、文法は文脈自由です。