文脈自由文法を仮定すると、生成された言語を調べることができますか？

Question

この文法で生成された言語を知るためにプロダクションルールを手動で適用する必要がありますか？これは面倒です、物事をスピードアップするためのトリック/ヒントはありますか？

G = {{S, B}, {a, b}, P, S} 
P = {S -> aSa | aBa, B -> bB | b} 

EDIT：私はMatajonの答え非終端記号によって生成された各言語について考えている良いものを、発見し、それらを組み合わせました。

しかし、私はこのようないくつかの複雑な例解決しなければならないとき、私はまだこだわっている：

G = {{S, R, T}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, P, S} 

P = {S -> A | AS | BR | CT, 
    R -> AR | BT | C | CS, 
    T -> AT | B | BS | CR, 
    A -> 0 | 3 | 6 | 9, 
    B -> 1 | 4 | 7, 
    C -> 2 | 5 | 8} 

クレイジーは、それではないでしょうか？過去の試験（プログラミング言語コース）から取得。

Answer 1

私は一般的なやり方は知らないが、通常、各非終端端末から生成される言語について考えるのがよい。

あなたのB言語から生成された言語は、明らかにL(B) = {b}^+です。次に、Sルールについて考えると、最初のルールを使用して、sentencialフォーム{a^n.S.a^n | n >= 1}を生成することができます。あなたがこれらのsentencialフォームまたはS単独でsentincialフォーム{a^n.B.a^n | n >= 1}を生成することができます2番目のルールを使用する場合。

残りは文法端子と非終端の定義では、あなたがこれらの二つのものを組み合わせて、ところでL(G) = {a^n.b^+.a^n | n >= 1}

を取得し、非常に簡単ですセット、ないタプルです。第3の要素は生産規則であり、開始記号ではありません。だから、G = {{S, B}, {a, b}, P, S}と書くべきです。

編集

実際には、多くの料理のようなものを、次のことで、単に何も考えずに自分の第二の例を解決する方法があります。なぜなら、第2の文脈自由文法によって生成された言語は、実際には規則正しいからです。

あなたが最初の3つの規則にA、BおよびCのルールを置き換えるとき、あなたは

P' = {S -> 0 | 3 | 6 | 9 | 0S | 3S | 6S | 9S | 1R | 4R | 7R | 2T | 5T | 8T 
    R -> 0R | 3R | 6R | 9R | 1T | 4T | 7T | 2 | 5 | 8 | 2S | 5S | 8S 
    T -> 0T | 3T | 6T | 9T | 1 | 4 | 7 | 1S | 4S | 7S | 2R | 5R | 8R} 

そしてP'を取得するには、定期的な文法です。そのため、非決定的な有限オートマトンに変換することができます（実際には簡単な方法があります）。結果のNFAを正規表現に変換することができます（これは単純ではありませんが、アルゴリズムに従って、 、あなたは大丈夫です）。そして、正規表現からは、それがどの言語で記述されているかを簡単に知ることができます。あなたは、この言語のためにNFAを持っていたら

また、あなたはそれを見て、それが論理的に何をするかを決定することができます（それは1,4,7と2,5,8言葉でその差のmod 3の数とは何かを持っている。それを通じ考えて、それをあなたの宿題である、afterall :-)）

もちろん、文脈自由な文法で普通の言語を生成していないなら、このトリックを使うことはできません。文法がどの言語を生成するかを知る一般的な方法はありません（CFGの言語平等問題は解決不可能です）、あらゆる単一の事例について考えて、その論理構造内で類似点とパターンを探す必要があります。

Answer 2

プロダクションルールを適用するだけでよいと思います。