2

私は実際にそれを持っているとかなり確信していますが、それは42の構築ルールを持っており、うまく一般化されていません。より少ない構築ルールでそれを行うにはどうすればよいですか？

言語は{a、b} *で、aの数はbの数の5倍です。

言語{a^n（連結）b ^ m; m=5n}それはただ

S = aSbbbbb | λ

しかし、キャラクターが任意の順序になっていると、私は迷子になります。

4

1 に答える 1

4

まず、文の文字数が他の文の 5 倍である場合、常に のようになることに注意してくださいaaabaabaaaaa。したがって、1つの文はaaaaabまたはになりaaabaaます。もう 1 つの観察事項は、 を追加するたびに、b5a文字を追加する必要があることです。

次の文法には、実際に文字数の 5 倍のa文字数がありbます。

S = AS | λ
A = Baaaaa | aBaaaa | aaBaaa | aaaBaa | aaaaBa | aaaaaB
B = bS | Sb

S空 (要件を満たす) か のどちらかから始めますA。

のルールでAは、少なくとも 5a文字とB. Bでは、配置bしてそこで停止するか ( に空の文字列を選択することにより)、または ( に を選択することにより)S再び開始することができます。これにより、常に文字数の 5 倍の文字数を配置することが保証されます。ASab

最後に、この文法は簡単に文法に一般化できますが、n( rule を単純に拡張することにより) 1 つの文字の何倍もの文字を含める必要がありますA。

于 2012-03-21T18:58:07.623 に答える