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
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:
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:
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.