HOME
Common Mistakes

Homework 1

	Closures. The closure of a set S under operation O is the minimal set that contains S and all the elements that result from applying O until you don't get any new elements. In the homework the question was the set of negative integers under the operation of division. You start constructing the closure by taking the original set, negative integers. Then you add the resulting elements after applying division by negative integers. So you add the positive rationals. Now you apply division by negative integers to the new elements in the set i.e. the positive rationals, you have to add negative rationals to your set. Now you apply division by negative integers to the new elements in your set, i.e. the negative rationals. You get back the positive rationals. Your set already had that, so you have a closure. Applying division by negative integers will not add any more elements to the set. The closure is thus negative integers, positive rationals and negative rationals, which is just the set of all rational numbers.
	Don't use truth tables. Give formal proofs with the rules for each step.
	Symmetric does not necessarily mean not anti-symmetric. Example: {(a, a), (b,b)} is both symmetric and anti-symmetric.
	The set of rational numbers is countably infinite, not uncountable. Here's a proof.

Homework 2

	The empty set (phi or {}) is not the same as the empty string epsilon. So {}* = {epsilon} != {}.
	The fact that a regular expression produces all the strings in a language doesn't mean that it is equivalent to the language: you must also make sure that the regular expression does not generate any string which is NOT in the language.

Homework 3

	While constructing a non-deterministic FSM make sure that it does not accept any string not in the language: note that for acceptance by a NDFSM existence of one path is sufficient while for strings not in the language there should not be ANY accepting path.
	For questions like 3, you have to prove your claim for any regular language, that is, if you are constructing a FSM for the new language, build it by modifying the FSM for the original language. Note however that you cannot assume anything about the structure of the FSM for the original language (See the next three points).
	In 3(a) making all states as a final state won't work: every state does not necessarily have a path to a final state.
	In 3(b) adding epsilon transition from the start state to all states would not work as every state need not be reachable from the start state.
	In 3(c) just making the final states which do not have a transition going out of it as a final state of the new FSM may not work because a final state may have all it's transitions going to dead states.

Homework 4

	When using the pumping lemma to prove that a language is not regular, your proof should work for any y, such that 0 < |y| <= N. Do not do a proof for a y with a particular known length such as 1.
	In the pumping lemma, the string that you pick from L is called w. w = xyz. After pumping, the string you get is no longer w, because it is xy^qz, where q != 1. If you're pumping down, q=0. If you're puming up, pick a q such that it is greater than or equal to 2. Pick a particular q.
	Remember the difference between a string and a language. A language can be regular or not. A string is just a string. Suppose L = { r : r is an element of {0,1}* and the number of 0's in r = the number of 1's in r}. You're trying to prove it is not regular using the pumping lemma. Pick w = 0^N 1^N. Now do NOT say that since we've proven in class that 0^N 1^N is not regular, then this string is not regular! and so L is not regular.

Homework 6

	Make sure that your grammar for a language does not accept any string not in the language.
	A rule like S-> P T P, where P and T are non terminals does not necessarily generate terms like xux, where x and u are in {0,1}* that is, even if you have the same non-terminal P, they won't generate the exact same string.
	The fact that some language needs counting and hence is not a regular language is a good intuitive thing. However, that does not constitute a proof.

Homework 7

	Question 1: PDA. Think of the end cases: such as epsilon, n=0, etc.
	Question 1: PDA .Does the order matter or not?
	Question 2 & 4: Your answer may not be correct, got points for putting down anything.
	Question 5: grammar => CNF. Write down each step.

Homework 8

	You cannot assume anything about the length of either v or y (other than the fact that |vxy| <=M)
	When you have strings of the form a*b*c* and you choose your w=a^M b^M c^M you cannot have v or y have more than one letter because that violates the order after pumping in. This case has to be mentioned in your proofs.

Homework 9

Union of two non-regular languages is not necessarily non-regular. Consider for eg L={a^nb^nc^n} and L'=(a U b U c)* - L. Both L and L' are not regular but L U L' is regular.

Homework 10

	Positive integers do not include 0.
	For 4(a) the input has to be checked to make sure it is of the form [x,y]
	A Recursive TM has both a accepting and rejecting halting state.

Homework 11

	Though you can have only terminals on the left hand side of a rule in an unrestricted grammar note that a string can be generated by not using all the rules.
	Whenever you're using a decision procedure without specifying what it is (like check if two DFAs are equivalent), it has to be one which has been done in the class and this fact has to be mentioned.

Homework 12

Do not confuse the TM M from the hard problem you are reducing from (eg the M from the halting problem) and the TM M* which you get from the reduction. For eg, In 4(c), M* should accept "M*M*" and reject "M*" [and not accept "MM" and reject "M"]