どのようにしてこの言語を生成する文法を構築できますか？文法、文脈自由文法

Question

私は有限オートマトン&文法テストのために勉強していると私はこの質問とこだわっている： L = {A^NB^MC^2N：

はLを生成文法を構築| n> = 0、m> = 0}

どのようにしてこの言語を生成する文法を構築できますか？ 文法文脈自由文法オートマトン

Answer 1

これはトリックを行うべきだと思います。 http://mdaines.github.io/grammophone/でこれを確認しました。
S - > a B c c | a S c c | 。
B - > b B | 。

Answer 2

私は、小さな文字列から大きな文字列を作成する方法のいくつかの規則を思いつくために、常にこの種の質問に役立つことがわかります。まず、あなたの言語でlittlest文字列を識別します。私たちの場合、n = 0の場合、b^mは私たちの言語であるという観測から始めることができます。つまり、b *の中のwは私達の言語です。 xが私たちの言語の文字列であれば、右にaを1つ追加して別の文字列を取得します。つまり、axccは私たちの言語の文字列です。だから、私たちのルールは以下のとおりです。L

で

1. のb * xの場合はLで、その後CFGの面でこれを書いLでaxcc

が今簡単です。

S -> B 
S -> aScc 

ここでSは言語Lを生成し、Bは言語b *を生成する。

(1) S -> B 
(2) S -> aScc 
(3) B -> e 
(4) B -> B 

任意の列A^NB^MC ^ルール2のn個のアプリケーションを使用して生成することができる2N、ルール1つのアプリケーション、m個のアプリケーション：我々は、開始シンボルBとb *のための文法を提供することによって、文法を完了しますルール4のルール1の適用と1のルール3の適用。この文法は言語に含まれない文字列を生成しないということは、練習問題として残されている。