Search code examples
closuresregular-languagecomputation-theory

Closure property of regular languages under concatenation and star operation

In our course of Theory of Computation, we have done the proof for closure of regular languages(L1, L2) under intersection, union and complement. But their closure under concatenation(L1L2) and star(L1*) operation was not done. It would be great if someone can explain me how can we prove these two.

Thanks in advance

Solution

  • The proofs of these facts are constructive.

    Let L1 and L2 be arbitrary regular languages. Because they are regular languages, we know there are minimal DFAs for L1 and L2; let's call these M1 and M2, respectively.

    To see that the concatenation of these languages must be regular, construct a machine M* as follows:

    • the states of M* are the states of M1 and M2 put together
    • the alphabet of M* is the union of the alphabets of M1 and M2
    • initial state of M* is the initial state of M1
    • accepting states of M* are the accepting states of M2
    • M* has all the same transitions as M1 and M2 put together, plus empty/epsilon/lambda transitions from all the accepting states in M1 to the initial state of M2

    This defines an NFA-lambda (NFA with empty/lambda/epsilon transitions). We know those are equivalent to DFAs and all DFAs can be minimized; let us call the equivalent minimal DFA M**.

    Because there is a minimal DFA for the concatenation of L1 and L2, the concatenation must be regular.

    The argument for L* where L is regular is similar. Let M3 be a minimal DFA for L. Then define M*** as follows:

    • States of M*** are the states of M3 plus an extra state q*
    • Alphabet of M*** is the alphabet of M3
    • Initial state of M*** is q*
    • Accepting state of M*** is q*
    • Transitions of M*** are the transitions of M3, plus empty/epsilon/lambda transitions from q* to the accepting state of M3, as well as empty/epsilon/lambda transitions from the accepting states of M3 to q*

    This defines an NFA-lambda (NFA with empty/epsilon/lambda transitions) which accepts L*. Because NFA-lambdas are equivalent to DFAs and DFAs can be minimized, there is a minimal DFA M**** for L*. As such, L* must be regular whenever L is.