Computation Theory 5: Closure of Regular Operations

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 A1 and A2. By the definition of a regular language there are two finite automata F1 and F2 that recognize each respectively. When combining A1 and A2 by a regular operation we want to creatively combine F1 and F2.  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 A1 and A2 be two regular languages with associated finite automata F1 and F2. Recall that the definition of  A1 ∪ A2 = {w | w ∈ A1 or w ∈ A2}.  Take a minute and think about how we can combine F1 and F2 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 F1 = {Q1, Σ1, q1, δ1, F1} and F2 = {Q2, Σ2, q2, δ2, F2}. Because we are going to need paths using states from both F1 and F2 we can set Q = {Q1 ∪ Q2}. The same is true for the set of accept states and alphabets, F = {F1 ∪ F2} 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 A1 it needs to traverse F1 and if it’s from A2 it needs to traverse F2. We need a piecewise transition function, if in A1 use δ1 and if in A2 use δ2. That just leaves how to get there.

Lets add a new start state to F, q0, such that we automatically go to q1 and q2 as soon as we start in the automata. We do this by connecting q0 to q1 and q2 by the ε path.  Then as soon as we start we jump to the start states of F1 and F2.

Lets take a stab at the transition function: δ = {δ(q0, ε) = {q1, q2}, δ(s, a) = δ1(s, a) if s is in Q1, δ(s, a) = δ2(s, a) if s is in Q2}. So we jump to the start states of F1 and F2 and follow the appropriate path.

Here is the formal definition of F:

  • Q = {Q1 ∪ Q2}
  • Σ = {Σ1 ∪ Σ2}
  • δ = {δ(q0, ε) = {q1, q2}, δ(s, a) = δ1(s, a) if s is in Q1, δ(s, a) = δ2(s, a) if s is in Q2}
  • q0
  • F = {F1 ∪ F2}

Exercise: Draw the state diagram of the NFA F for two finite automata F1 and F2.

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, A1 and A2, is
A1 • A2 = {sw | s in A1 and w in A2}. (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 A1 followed by a string in A2.

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 A1 and A2 be regular languages with associated finite automata F1 and F2. Let F1 = {Q1, Σ, q1, δ1, F1} and F2 = {Q2, Σ, q2, δ2, F2}. 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 A1 by a string from A2 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 A1? Do we know where it will end? The answer is that by definition it will end on an accept state of A1 so we don’t have to have a path from all states of F1 to F2 we just need paths from the accept states of A1.

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

Formal definition for F:

  • Q = {Q1 ∪ Q2}
  • Σ
  • q0 = q1
  • δ = {δ(s, a) = δ1(s, a) if s in A1 and a ≠ ε, δ(s,ε) = q2 for s in F1, δ(s, a) = δ2(s, a) for s in Q2}
  • F = F2

Exercise: Draw the state diagram of F for two finite automata F1 and F2.

Star:

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

  1. Define A and its associated finite automata.
  2. Construct each of the required definition elements for the automata F associated to A*.
    1. What are the states?
    2. What is the language?
    3. What is the start state?
    4. What are the transitions?
    5. What are the accept states?
  3. Verify that what you have constructed does actually work.
  4. Hint: What happens if you replace A2 in the concatenation proof with A1.

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

post-35400-How-to-draw-an-owl-meme-HUo8

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.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s