**Introduction:**

In this module we are going to talk about the closure of regular operations with respect to regular languages. In plain terms, if we take two regular languages and use one of the previously discussed operators on them we will have another regular language. Recall that we have previously talked about the operations of union, concatenation, and star. Recall as well that a language is regular if there is a finite automaton that recognizes it.

*Exercise*: See if you can write down the definition of each of the three operations on regular languages without looking them up again.

Lets discuss the idea of what we need to do for each of these operations. We are going to use the same type of constructive proof that we did in the last module. That is we are going to explicitly construct a finite automaton that recognizes the new language. We are going to use the finite automata that recognize the original languages.

Here’s what’s going to happen. We will assume we have two regular languages A_{1} and A_{2}. By the definition of a regular language there are two finite automata F_{1} and F_{2} that recognize each respectively. When combining A_{1} and A_{2} by a regular operation we want to creatively combine F_{1} and F_{2}. The hope is that if we are creative in our construction the new finite automata will recognize the new language, and if we did it correctly it will. As a hint we have the property that for every NDA there is an equivalent DFA, so all we need to finish the proof is an NFA that recognizes the new language. As you are reading through the proofs try to predict what the next step is before you read it.

**Union:**

Let A_{1} and A_{2} be two regular languages with associated finite automata F_{1} and F_{2}. Recall that the definition of A_{1} ∪ A_{2} = {w | w ∈ A_{1} or w ∈ A_{2}}. Take a minute and think about how we can combine F_{1} and F_{2} so that if we are given a string w it will jump to the correct automata path.

If we think about NFA’s there is a path that is automatically taken when we land on a state with it as an exit path. Can you think of a way to use that type of path to jump to the correct execution path? Lets write down some formal definitions to get things going.

Let F_{1} = {Q_{1}, Σ_{1}, q_{1}, δ_{1}, F_{1}} and F_{2} = {Q_{2}, Σ_{2}, q_{2}, δ_{2}, F_{2}}. Because we are going to need paths using states from both F_{1} and F_{2} we can set Q = {Q_{1} ∪ Q_{2}}. The same is true for the set of accept states and alphabets, F = {F_{1} ∪ F_{2}} and Σ = {Σ_{1} ∪ Σ_{2}}.

We don’t really know where to start yet so lets think about the transition function. What do we know about how the new finite automata will be traversed by strings? If the string comes from A_{1} it needs to traverse F_{1} and if it’s from A_{2} it needs to traverse F_{2}. We need a piecewise transition function, if in A_{1} use δ_{1} and if in A_{2} use δ_{2}. That just leaves how to get there.

Lets add a new start state to F, q_{0}, such that we automatically go to q_{1} and q_{2} as soon as we start in the automata. We do this by connecting q_{0} to q_{1} and q_{2} by the ε path. Then as soon as we start we jump to the start states of F_{1} and F_{2}.

Lets take a stab at the transition function: δ = {δ(q_{0}, ε) = {q_{1}, q_{2}}, δ(s, a) = δ_{1}(s, a) if s is in Q_{1}, δ(s, a) = δ_{2}(s, a) if s is in Q_{2}}. So we jump to the start states of F_{1} and F_{2} and follow the appropriate path.

Here is the formal definition of F:

- Q = {Q
_{1}∪ Q_{2}} - Σ = {Σ
_{1}∪ Σ_{2}} - δ = {δ(q
_{0}, ε) = {q_{1}, q_{2}}, δ(s, a) = δ_{1}(s, a) if s is in Q_{1}, δ(s, a) = δ_{2}(s, a) if s is in Q_{2}} - q
_{0} - F = {F
_{1}∪ F_{2}}

*Exercise*: Draw the state diagram of the NFA F for two finite automata F_{1} and F_{2}.

As you can see the main part of the problem in this construction is getting the right path through the new set of states. That will be the theme of the next proofs as well.

**Concatenation:**

Recall that the definition of concatenation for two languages, A_{1} and A_{2}, is

A_{1} • A_{2} = {sw | s in A_{1} and w in A_{2}}. (I’m using the closed circle to denote concatenation instead of the open circle for lack of symbol support). Which in plain terms means that we have a string in A_{1} followed by a string in A_{2}.

There is a property that is inherent in the definition of a regular language that limits some of what we have to worry about in the new transition function. See if you can think of what it is. After you’ve thought about it for a minute lets get on to the proof.

Let A_{1} and A_{2} be regular languages with associated finite automata F_{1} and F_{2}. Let F_{1} = {Q_{1}, Σ, q_{1}, δ_{1}, F_{1}} and F_{2} = {Q_{2}, Σ, q_{2}, δ_{2}, F_{2}}. We may go ahead and just use one symbol for the alphabet because it doesn’t change anything by using the same alphabet for both automata.

If we are going to follow a string from A_{1} by a string from A_{2} we need a way to get from the end of one string to the beginning of the next. What can we say about the end of a string from A_{1}? Do we know where it will end? The answer is that by definition it will end on an accept state of A_{1} so we don’t have to have a path from all states of F_{1} to F_{2} we just need paths from the accept states of A_{1}.

We are going to make use of the ε path again. Think about where we want to connect to in F_{2} from the accept states of F_{1}. Lets go ahead and make the definition for the new NFA from F_{1} and F_{2}.

Formal definition for F:

- Q = {Q
_{1}∪ Q_{2}} - Σ
- q
_{0}= q_{1} - δ = {δ(s, a) = δ
_{1}(s, a) if s in A_{1}and a ≠ ε, δ(s,ε) = q_{2}for s in F_{1}, δ(s, a) = δ_{2}(s, a) for s in Q_{2}} - F = F
_{2}

*Exercise: *Draw the state diagram of F for two finite automata F_{1} and F_{2}.

**Star:**

For this operation I’m going to let you come up with the proof. Recall that the definition of A* = {w_{0}w_{1}…w_{n} | for all k ≤ n, w_{k} in A}. I’ll provide an outline of what you need to do:

- Define A and its associated finite automata.
- Construct each of the required definition elements for the automata F associated to A*.
- What are the states?
- What is the language?
- What is the start state?
- What are the transitions?
- What are the accept states?

- Verify that what you have constructed does actually work.
- Hint: What happens if you replace A
_{2}in the concatenation proof with A_{1}.

Hopefully that isn’t too much like learning to draw an owl:

**Conclusion:**

Now we have that when we combine two regular languages with a regular operation we have a new regular language. Note that each of these proofs hinged on the fact that for every NFA there is an associated DFA. Without that result we would have had to make a different construction.