Exam 1 Results

Scores

There were 79 scores (72 nonzero scores and 7 zeros for people who cheated on the exam):

• 100
• 85 82 81 80 80 80
• 79 79 79 77 75 75 75 74 74 74 74 73 72 72 71
• 69 69 68 67 67 66 65 65 64 64 64 64 63 63 63 62 62 61 61 60
• 59 59 58 57 57 57 56 55 55 54 52 52 52 52 51 50 50
• 49 47 47 46 45 43 43 41 40
• 35 31
• 25 25
• 0 0 0 0 0 0 0

Statistics

• Mean = 56.2 (61.7 excluding zeros).
• Standard deviation = 22.4 (14.5 excluding zeros).

Comments on Exam 1 Problems

Problem 1

It might help if you think of the Pumping Lemma as (claiming the existence of) a function on languages that yields a natural number and a function on strings: PumpingLemma: Language → N × (Σ* → Σ* × Σ* × Σ*). If L is regular, then PumpingLemma(L) = (K, f). The lemma promises that for every w ∈ L where |w| > K, the function f will return an ordered triple of strings with certain guaranteed properties: f(w) = (x, y, z), w = xyz, |xy| ≤ K, |y| > 0, and every xy^kz ∈ L. On the other hand, the lemma says nothing about how f behaves on w of lengths ≤ K, and it doesn’t give you any information about x, y, or z other than the relationships mentioned above. So you can’t base your analysis on the assumption that y has length 1, for example, unless you also analyze the cases where y has a length other than 1.

Or it might help to think of the contrapositive of the Pumping Lemma: If for every constant K > 0, there exists a string w ∈ L such that for all x, y, z ∈Σ* where w = xyz, |xy| ≤ K, and |y| > 0, there exists an exponent k such that xy^kz ∉ L, then L is not regular.

Problem 3

Comment C1

A number of people tried to take a DFA M for L and build an NFA N for Ends(L) by replacing intermediate transitions in M with e-moves. This turns out to be tricker than it seems because of transitions into and out of start and final states. For example, depending on the details of the construction, you might have turned the first automaton below into the second. Ends(L) for the left hand automaton is { ab, ac, bb, bc }, but the right hand automaton accepts (a ∪ c)*.

Comment C2

Let First(L) be the set of first characters of strings in L and let Last(L) be the set of last characters of L. Then Ends(L) is a subset of the concatenation First(L) Last(L), but possibly a strict subset. Example: L = { aaa, bbb }, First(L) = Last(L) = { a, b }, Ends(L) = { aa, bb }, First(L) Last(L) = { aa, ab, ba, bb }.

Comment C3

You can’t prove regularity using the pumping lemma. The lemma has the form if regular then pumping condition. The converse, if pumping condition then regular, is false.

Comment C4

The union of an infinite number of regular sets doesn’t have to be regular. For example, { e }, { ab }, { aabb }, { aaabbb }, ... are each regular sets (since they have only one element each), but their union is the language { aⁿbⁿ | n ≥ 0 }, which is not regular.

For our problem, for each xzy ∈L, the singleton string language { xy } is regular, but this doesn’t prove that Ends(L) is regular.

Comment C5

For any language L (even non-regular ones), the subset of L restricted to strings of length n ≥ 0 is regular (since it’s finite). For example, { e }, { e, ab }, { e, ab, aabb }, { e, ab, aabb, aaabbb }, ... are each regular sets, but the limit set { aⁿbⁿ | n ≥ 0 } isn’t.

So you can’t prove that a language is regular by looking at its length-restricted subsets. In particular, you can’t prove that Ends(L) is regular by induction on the length of strings in L.

Problem 4

Problem 6

Let L be the language denoted by (ab ∪ aba)*; there are five equivalence classes under L. The classes [e] and ∅ are trivial; the other three classes are nontrivial.