Search code examples
regextheoryregular-language

A regular expression for repeated, interleaved copies of a string?

Find a regular expression for this language:

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

Ok so I have been working of this problem for sometime now. So far I know that 'ab' repeats its self (ab). But I am stumped on 'ac'.... it cant be (ab)(ac)*... Any pointers would be appreciated.

I've looked at my book and there is not example that can show me how to solve this.

Solution

  • Let's start by simplifying things a bit. Let's let B denote ab and C denote ac. Then you are trying to generate the strings

    λ, B, BC, BCB, BCBC, BCBCB, ...

    In this case, you might want to split the regular expression into two cases: one that generates

    λ, BC, BCBC, BCBCBC, BCBCBCBC, ...

    and one that generates

    B, BCB, BCBCB, BCBCBCB, ...

    The former is given by the regular expression (BC)*, and the latter is given by the regular expression (BC)*B. If you combine these together, you get (BC)* | (BC)*B, which could be rewritten as (BC)*(B | λ). All that's left to do is expand this out by replacing B and C withabandac`, which gives the resulting regular expression

    (abac)*(ab | λ)

    This observation should also let you design a DFA or NFA for the language, but I'll leave that as an exercise. :-)

    Hope this helps!