L={w∈{a,b,c}*|w has more as than bs} の文脈自由文法の作り方
質問する
95 次
1 に答える
0
まず、プッシュダウン オートマトンの形式で考えることで、それが可能であると自分自身に納得させることができます。非公式: テープを読み取るときは、"a" をスタックにプッシュしますが、"b" を読み取るときはスタックをポップします。テープの読み取りが終了したら、スタックに「a」があれば受け入れます。それ以外の場合は拒否します。
CFG: 基本的に、"b" が作成されるたびに少なくとも 1 つの "a" が混在するように、文法をバインドする必要があります。
ヒント：
- "c" を少し無視します
- 有効な言語の開始と終了の方法 (基本的には 2 つの文字の組み合わせ) を書き留め、そこから一般化してみてください。
于 2012-07-15T11:10:13.690 に答える