Closure Proof Template

CSE 105 Spring 2004
Cynthia Bailey Lee, T.A. Comments? Questions? Did you use this page for your class (either as a student or instructor)? Feel free to email me

[Problems 1.24, 1.32, and 1.42 in the textbook (Michael Sipser, Introduction to the Theory of Computation) also follow this template. We will do a really simple example here so you get the idea of the template. Note: There is an easier way to prove this example--you need to know how to do it both ways.]

Template Example Explanation

PROBLEM:
If A is a regular language, show that language A' = { some transformation of A } is also regular.

Problem: If A is a regular language, show that language A' = { w | w = x1 for some x in A } is also regular. (Alphabet is {0,1}.) Closure proofs are problems that ask the question, "If I have a regular language, and do [blah] to it, is the new language still a regular language?"
Our example problem is asking&emdash;if you take a regular language, and add a "1" to the end of everything in it, is the new language also regular?
Whenever you see a problem like this, use the template in the left column to solve it. What you would actually write on your test or HW is shown in the example in the middle column.
If you need a very quick explanation of the word "closure" before continuing, check here: Overview of set closure.

GIVEN:
A is regular, so there is a DFA M = (Q, Σ, δ, q₀, F) that recognizes A.

Given: A is regular, so there is a DFA M = (Q, Σ, δ, q₀, F) that recognizes A. The first thing you should always do when solving these problems is write this sentence (see in the example I just copied it.) What you are saying here is what is already known. You already know that A is regular. So what does that mean? That means that there must be some DFA that recognizes A. We will need to use that DFA later, so we give it a name, M, and while we're at it, we give names to its individual parts (Q, Σ, δ, q₀, F) so we can talk about them later too.
Why did we pick a DFA? We know that A must have an NFA that recognizes it as well. The reason we choose to start with a DFA is that the rules for the structure of DFA's are a little "stricter" than those for NFA's (for example, DFA's can only have one outgoing edge per state per input character). That may make our job easier later on.

WANT:
To show language A' is regular. We will build an NFA M' that recognizes A'.

Want: To show language A' is regular. We will build an NFA M' that recognizes A'.
Again, you should always copy this sentence exactly. You are just announcing to the reader what you are doing. What are we doing? We want to prove that A' is regular. How can we do that? If we can show that some NFA recognizes A', then we will have proved that A' is regular. So that's the plan.
Why are we using an NFA? Didn't we just decide that DFA's are easier to work with (in the "Given" section)? Because we will be building M', we would like to have as few restrictions on the structure of what we're building as possible. So in this case, the "loose" rules of the NFA are an advantage.

CONSTRUCTION:
Let M' = (Q', Σ', δ', q₀', F'), where:

Q' = some transformation of Q
Σ' = usually just the same as Σ, plus ε since it is an NFA
δ' = some transformation of δ
q₀' = some transformation of q₀
F' = some transformation of F

[Optional: A couple sentences of regular English description of the above could go here.]

Construction: Let M' = (Q', Σ', δ', q₀', F'), where:
Q' = Q U {q_x} ("U" here and on the next line means "union")
Σ' = Σ U {ε}
δ'(q, σ) = {
q_xif q is in F and σ = 1
δ(q, σ) if q is in Q
Ø otherwise
} q₀' = q₀
F' = {q_x}
We add a new final state q_x and make an edge from every old final state to q_x for the input character 1.
Until now, you've just been copying sentences from the template. Now some problem-specific thinking is required. You need to think about how you can change the DFA M to an NFA M' that recognizes A'. The "official" way to do this is to specify the components of M'.
You should draw some examples and state diagrams to help you think of how to solve it, then once you have your idea, translate it to this formal language.
Though they are not part of the proof, some DFA/NFA drawings or a few sentences of regular English describing what you are trying to do may get you some partial credit on a quiz if there are some minor errors in your formal description.
Remember how we decided to make M' be an NFA instead of a DFA? That helped us here, because when we added a '1' edge from the old final states to the new final state, we created a second outgoing '1' edge for those states (they already had an outgoing '1' edge). Because NFA's allow this, our solution works. Our job would have been much trickier if we were trying to make a DFA, which only allows one outgoing edge per input per state.

CORRECTNESS:
(1) Let x be a string in A'. [prove that M' accepts x] Therefore M' accepts x. (2) Let x be a string not in A'. [prove that M' rejects x] Therefore M' rejects x.

Correctness:
(1) Let x be a string in A'. Then x = a1 where a is a string in A. Then the computation of a on M ends in a state in F. Then the computation of the a part of x on M' will end in a state in F. Then the next input is '1', so we end in q_x, so M' accepts x.

(2) Let x be a string not in A'. If the computation of x, up to the last character, on M ends in a state in F, then the last character must be '0' (else x would be in A'), so the computation of x on M' cannot end in q_x, so M' rejects x. If the computation of x, up to the last character, on M does not end in a state in F, then no matter what that last character is, the computation of M' cannot end in q_x, so M' rejects x.
This section, a correctness proof of the NFA you have constructed, is optional for the quiz. You should still consider the two cases in your mind to make sure your solution is correct, and some outline of a correctness argument may help you get partial credit on the quiz. (The "Conclusion" below is required.)
Here we need to prove that the thing we made in the construction part actually works. There are two steps to this proof. (1) We need to show that M' accepts everything in A'. (2) We also need to show that M' does not accept anything that is not in A'.

CONCLUSION:
M' recognizes A', so A' is regular. QED.

M' recognizes A', so A' is regular. QED. To finish your proof, make sure that you have proved what you set out to prove. In this case, we demonstrated the existence of an NFA that recognizes A', therefore our original claim, that A' is regular, must be true.
QED is a fancy Latin acronym that means your proof is done (optional).

Pop Quiz! What are the parts of a closure proof? (PROBLEM), GIVEN, WANT, CONSTRUCTION, CORRECTNESS, CONCLUSION. GWCCC!! Memorize it!

Template	Example	Explanation
PROBLEM: If A is a regular language, show that language A' = { some transformation of A } is also regular.	Problem: If A is a regular language, show that language A' = { w \| w = x1 for some x in A } is also regular. (Alphabet is {0,1}.)	Closure proofs are problems that ask the question, "If I have a regular language, and do [blah] to it, is the new language still a regular language?" Our example problem is asking&emdash;if you take a regular language, and add a "1" to the end of everything in it, is the new language also regular? Whenever you see a problem like this, use the template in the left column to solve it. What you would actually write on your test or HW is shown in the example in the middle column. If you need a very quick explanation of the word "closure" before continuing, check here: Overview of set closure.
GIVEN: A is regular, so there is a DFA M = (Q, Σ, δ, q₀, F) that recognizes A.	Given: A is regular, so there is a DFA M = (Q, Σ, δ, q₀, F) that recognizes A.	The first thing you should always do when solving these problems is write this sentence (see in the example I just copied it.) What you are saying here is what is already known. You already know that A is regular. So what does that mean? That means that there must be some DFA that recognizes A. We will need to use that DFA later, so we give it a name, M, and while we're at it, we give names to its individual parts (Q, Σ, δ, q₀, F) so we can talk about them later too. Why did we pick a DFA? We know that A must have an NFA that recognizes it as well. The reason we choose to start with a DFA is that the rules for the structure of DFA's are a little "stricter" than those for NFA's (for example, DFA's can only have one outgoing edge per state per input character). That may make our job easier later on.
WANT: To show language A' is regular. We will build an NFA M' that recognizes A'.	Want: To show language A' is regular. We will build an NFA M' that recognizes A'.	Again, you should always copy this sentence exactly. You are just announcing to the reader what you are doing. What are we doing? We want to prove that A' is regular. How can we do that? If we can show that some NFA recognizes A', then we will have proved that A' is regular. So that's the plan. Why are we using an NFA? Didn't we just decide that DFA's are easier to work with (in the "Given" section)? Because we will be building M', we would like to have as few restrictions on the structure of what we're building as possible. So in this case, the "loose" rules of the NFA are an advantage.
CONSTRUCTION: Let M' = (Q', Σ', δ', q₀', F'), where: Q' = some transformation of Q Σ' = usually just the same as Σ, plus ε since it is an NFA δ' = some transformation of δ q₀' = some transformation of q₀ F' = some transformation of F [Optional: A couple sentences of regular English description of the above could go here.]	Construction: Let M' = (Q', Σ', δ', q₀', F'), where: Q' = Q U {q_x} ("U" here and on the next line means "union") Σ' = Σ U {ε} δ'(q, σ) = { q_xif q is in F and σ = 1 δ(q, σ) if q is in Q Ø otherwise } q₀' = q₀ F' = {q_x} We add a new final state q_x and make an edge from every old final state to q_x for the input character 1.	Until now, you've just been copying sentences from the template. Now some problem-specific thinking is required. You need to think about how you can change the DFA M to an NFA M' that recognizes A'. The "official" way to do this is to specify the components of M'. You should draw some examples and state diagrams to help you think of how to solve it, then once you have your idea, translate it to this formal language. Though they are not part of the proof, some DFA/NFA drawings or a few sentences of regular English describing what you are trying to do may get you some partial credit on a quiz if there are some minor errors in your formal description. Remember how we decided to make M' be an NFA instead of a DFA? That helped us here, because when we added a '1' edge from the old final states to the new final state, we created a second outgoing '1' edge for those states (they already had an outgoing '1' edge). Because NFA's allow this, our solution works. Our job would have been much trickier if we were trying to make a DFA, which only allows one outgoing edge per input per state.
CORRECTNESS: (1) Let x be a string in A'. [prove that M' accepts x] Therefore M' accepts x. (2) Let x be a string not in A'. [prove that M' rejects x] Therefore M' rejects x.	Correctness: (1) Let x be a string in A'. Then x = a1 where a is a string in A. Then the computation of a on M ends in a state in F. Then the computation of the a part of x on M' will end in a state in F. Then the next input is '1', so we end in q_x, so M' accepts x. (2) Let x be a string not in A'. If the computation of x, up to the last character, on M ends in a state in F, then the last character must be '0' (else x would be in A'), so the computation of x on M' cannot end in q_x, so M' rejects x. If the computation of x, up to the last character, on M does not end in a state in F, then no matter what that last character is, the computation of M' cannot end in q_x, so M' rejects x.	This section, a correctness proof of the NFA you have constructed, is optional for the quiz. You should still consider the two cases in your mind to make sure your solution is correct, and some outline of a correctness argument may help you get partial credit on the quiz. (The "Conclusion" below is required.) Here we need to prove that the thing we made in the construction part actually works. There are two steps to this proof. (1) We need to show that M' accepts everything in A'. (2) We also need to show that M' does not accept anything that is not in A'.
CONCLUSION: M' recognizes A', so A' is regular. QED.	M' recognizes A', so A' is regular. QED.	To finish your proof, make sure that you have proved what you set out to prove. In this case, we demonstrated the existence of an NFA that recognizes A', therefore our original claim, that A' is regular, must be true. QED is a fancy Latin acronym that means your proof is done (optional).

Alternate (easier) proof:

Problem:
If A is a regular language, show that language A' = { w | w = x1 for some x in A } is also regular. (Alphabet is {0,1}.)

We solved this problem above using the construction proof template so you could see concretely that template in action. But there is an easier way to prove this problem.

Recall in class and discussion we talked about using the closure properties of regular languages that we learned in class as a "trick" to make proofs easier. The closure properties we learned in class are:

Union: the union of two regular languages is also a regular language.
Intersection: the intersection of two regular languages is also a regular language.
Concatenation: the concatenation of two regular languages is also a regular language.
Complement: the complement of a regular language is also a regular language.
"*" Operator: the concatenation of 0 or more strings in a regular language is also a regular language.

On the quiz, you can assume any of these properties of regular languages and use them (without having to re-prove them). How can you use one of these properties, or a combination of them, to solve our example problem? (Try to solve it on your own first! Then scroll down.)

Solution:
Our language A' is just the the set of strings in language A, with a "1" appended to the end of each. What is another word for "appended"? How about "concatenated"? The language A' is the concatenation of two languages: A and B, where language B = {"1"}. We know A is regular, what about B? You can easily make a DFA that recognizes B, right? So B is also regular. Written formally, the proof would look like this:

Given: A is a regular language.
Want: Want to show that A' is a regular language.
A' = A concatenated with B, where B = {"1"}. B is a regular language [this is pretty obvious but if want to be very rigorous you could give the formal description of a DFA that recognizes B]. Since A' is the concatenation of two regular languages, and we know regular languages are closed under concatenation, then A' is also regular. QED.