regex - インターリーブされた文字列の繰り返しコピーの正規表現?

Question

この言語の正規表現を見つけます:

L = {λ, ab, abac, abacab,abacabac, abacabacab,...}

わかりましたので、私はしばらくの間この問題に取り組んできました。これまでのところ、「ab」がその自己 (ab) を繰り返すことを知っています。しかし、私は「ac」に困惑しています....それは（ab）（ac）*ではありません...どんなポインタでもいただければ幸いです。

私は自分の本を見てきましたが、これを解決する方法を示す例はありません。

Answer 1

物事を少し単純化することから始めましょう。abB を、C を としましょうac。次に、文字列を生成しようとしています

λ、B、BC、BCB、BCBC、BCBCB、...

この場合、正規表現を 2 つのケースに分割することをお勧めします。

λ、BC、BCBC、BCBCBC、BCBCBCBC、...

そして生成するもの

B、BCB、BCBCB、BCCBCBCB、...

前者は正規表現(BC)*で与えられ、後者は正規表現で与えられます(BC)*B。これらを組み合わせると(BC)* | (BC)*Bとなり、これは と書き換えることができます(BC)*(B | λ)。あとはab ac` を置換してこれを展開するだけですB。これにより、結果の正規表現が得られます。C withand

(abac)*(ab | λ)

この観察により、言語の DFA または NFA を設計することもできますが、それは演習として残します。:-)

お役に立てれば！