これは宿題に関する質問ですが、質問をできるだけ早く理解することが重要でないかどうか私はここでは質問しません。文脈自由文法の一部大きな謎
私は言語{w、{b、b} *}を与えられました。 wはa^n b^m yの形式であり、ここで| y | = n + m}文脈自由文法を作らなければならない。
私はこの問題は、私の解決策（私の最高の推測）のために、私の理解で問題があると思う：
S - >には| bB | _（ "_" 空の意味）
B - > BBY
は、 "文字列あなたの文法を使用して生成することができませんでした 'aaaaba'" と、このようなのようなエラーを生成します。誰かが正しいトラックに私を助けることができますか？どうやら私は「y」と書かなければならないと思うので、その機能は何ですか？私はウェブ上の例を探してみましたが、| x = z + kなどがないものは見つかりませんでした。
お願いします。
表記は少し奇妙ですが、私はあなたの言語がa秒、その後、b秒の後、いくつかの数、a sおよび/またはbの数のいくつかの数からなるすべての文字列の集合であると仮定しています最初の2つの部分の合計数はa秒、b秒です。
これが正しい場合、既存の文法にはいくつかの問題があります。まず、Sのプロダクションは、最初の2つのパートの文字と3番目のパートの文字のバランスを保つことを確実にするつもりはありません。次に、Bは決して一連の端末記号に解決されません。それは縛られることなく永遠に成長するでしょう。
言語が間違っている場合は、私を修正してください。あなたはN B メートル部分が生成されるよう
私はそれをどのように読んでいるのかについての明確化：私は 'y'が3番目の部分（すなわち、長さが前の2つの合計に等しいもの）であると考えていると思います。 「w in {a、b} *」と書かれている部分は、なぜ「a」と「b」だけで構成されていると仮定しているのですか。この場合、 'y'は文脈自由文法の中のシンボルに対応しません。なぜなら、どれくらいの時間があるかを知ることができないからです。 – Taymon
最終yは、できるだけ多くの文字が含まれている必要がありますので、あなたも非終端後に手紙を生成する必要があります。
S -> aSa | aSb | B
B -> -- well, I'll leave a bit of the homework to you
可能重複[ためのCFGを作成]（http://stackoverflow.com/questions/9406382/construct-a-cfg-for） –
それは近いですが、追加のYは、端部にありますこの関数は謎です（a^nb^my？）。ありがとう、結構です。 – user1258216