Typical mistakes on Test 1, CS 3350, Fall 2015


1. To prove something by contradiction, you need to show that
there is indeed a contradiction, i.e., that under the given
assumption, we can prove some statement and the negation of this
statement.

In the proof that the square root of 2 is irrational, we first
show that we can always have a ratio m/n in which m and n have no
common divisors -- since we can always divide both the numerator
and the denominator by a common divisor without changing the
ratio.

Then we show that if m/n is equal to the square root of 2, then m
and n have a common divisor -- namely, a common divisor 2.

A similar explicit contradiction is needed here as well.

2. A typical mistake is using the wrong scheme for the
non-deterministic finite automaton for concatenation AB of two
languages A and B. To get concatenation, we keep the automaton B
intact, but the final states of the automaton A are no longer
final. All states that were final for A are now connected by a
hump to the starting state of B.

3. For each state of the resulting deterministic automaton and for
each symbol from the corresponding alphabet, we need to describe
where we go next.

You do not need to do that for a non-deterministic automaton --
this is why it is non-deterministic, but for a deterministic
automaton, you need to explicitly tell what to do in each
situation.

4. To describe a regular expression corresponding to a finite
automaton, one needs to add two new states to this automaton: a
new start state n, from which there is a jump to the previous
start state, and a new final state f, to which there is a jump
from all previously final states.

For example, if in the original automaton, q1 was the only final
state, there should be a jump from q1 to f, but no jump from q2 to
f.

Also, it is important not to confuse concatenation with union. For
languages A = {a} and B = {b}, the union A U B consists of two
words a and b, while the concatenation AB consists of a single
word ab.

5. In the pumping lemma, the length of xy is bounded by p, and p
is the number of states in the automaton (maybe +1). for an
automaton with two states, xy should be contained within the first
two or three first symbols of the accepted string.

A sure way to guarantee this is to consider the first repeating
pair, not the second or the third one.

6. The plan was for you to follow the original proof -- which you
should have had as part of your cheat sheet -- and only modify
what is needed for this particular problem. Those who followed
this plan succeeded, while many of those who improvised instead
did not get the correct proof.

For example, it is important to remember that the representation
of a word s as xyz is possible only for words s of length p or
larger, and we do not know p beforehand. So, you cannot just use
any word s like 010010, since there is no guarantee that its
length will be at least p, you need to explicitly use p when
building an example.