(2)がわかりません、、 教えてください。 "0と1から成る、1を3の倍数個含む集合" だと考えたの

(2)がわかりません、、
教えてください。

"0と1から成る、1を3の倍数個含む集合"
だと考えたのですが、多分違いますよね？

No.1 ベストアンサー 回答者： ゼロプライム 回答日時： 2020/03/26 23:02

"0と1から成る、1を3の倍数個含む集合"　合っています。

１を３の倍数個含むということで、１が０個の列も含まれているということだと思いますが、０と１か
ら成ると表現されているので、ちょっと誤解されやすい表現です。０だけの列、1だけの列も含むと一
言添えると親切だと思います。

①０だけからなる列は、どんな長さの列も存在します。

②S→１Aにより、１を生成した場合は、最も短くても長さ３の列になってしまいます。
S→１A、A→１B、B→１とすると、１１１が生成されます。
１が1個や2個の列は生成することができません。０については、１の前、間、後にいくつでも生成できますので、１を3個含む列の長さは３以上になります。

③S→１A、A→１B、B→１Sとすると、１１１が生成されその後も続きますが、S→１Aにより、４個目
の１を生成した場合は、②と同じことを繰り返しますので、１が4個や5個の列は生成できません。よっ
て、１を6個含む列になり、その長さは６以上になります。

⓸以下同様ですが、7個目の１を生成すると、１の個数は９個になり、列の長さは９以上になります。

このようにして列が生成されますので、この文法により生成される列の集合は次のようになります。
０と１から成る列の集合で、その列に含まれる１の個数は３の倍数個、０の個数は制限はありません。
ただし、０だけからなる列、１だけからなる列も含みます。

この回答へのお礼

ご丁寧な解説ありがとうございます。
解決しました！

お礼日時：2020/03/27 20:14