- Again, many people couldn't keep their alphabets straight, writing a,b,c or i,j,k instead of d,e,f. I will deduct points for this in the future.
- A couple of people misread problems and were confused about which exponents where equal to each other and which were less than each other. This is a very basic error that I don't expect to see again.
- Several people who used the 3rd pumping theorem for CFLs thought that vwx was a substring of z2. That is incorrect. You are guaranteed only that v or x is a substring of z2. If you were guaranteed that v and x were substrings of z2 then you could prove that the CFL {anbn : n ≥ 0} is not a CFL by letting z1 = Λ, z2 = aN, and z3 = bN.
- Many people left out several possible cases for v and x, or failed to explain why those cases don't occur.
- I am still seeing some of the same errors I saw on Quiz 7.
The final will be Tuesday May 8 at the regular class time and place.
- In the anbncn problem, you have to prove that vx cannot contain a's and c's.
- There are still some problems with the order of the steps. They should be
- There exists a pumping number N
- Let z = .... Then z is in L and |x| ≥ N. Do not write "let z ε L"
- There exist u,v,w,x,y such that ...
- Then v and x have certain useful properties (which have to be proved)
- Let i = .... Then uviwxiy is not in L.
- v and x might not have to have the same length.
- In the an2 problem, you can't conclude that v=ak and x=ak. In fact, v could be ak and x could be am where m ≠ k
- In the anbncn problem, v could be ak and x could be bm where m ≠ k
- In the anbncn problem, v and x might not contain different characters, e.g., you could have v=bk and x=bm where m ≠ k
- After you have proved that v=ak for some value of k, you still can't chose u, w, x, and y.
- If you use the third pumping theorem for CFLs, you have to choose z1, z2, and z3 such that z1z2z3 is in L and |z2| ≥ N.
- If you use Ogden's theorem, you have to make sure weight(z) ≥ N before you conclude there exist u, v, w, x, and y
- If you use the third pumping theorem for CFLs, you can't conclude vwx = z2. Instead, write that v is a substring of z2 or x is a substring of z2.
- It's not enough to just write "by pumping up once." You should at least write uv2wx2y
- Try to keep your characters straight. If the question involves 0's, 1's, and 2's, the answer shouldn't involve a's, b's, and c's (unless you perform a finite transduction).
- Don't write "z=uviwxiy"
- Instead of "more number of" write "more"
- Instead of "has number of a's greater than number of b's" write "has more a's than b's"
- Instead of "the number of characters contained by v" write "|v|" or "the length of v"
- Instead of "1 ≤ v ≤ N" write "1 ≤ |v| ≤ N"
- Instead of "|v| ≠ Λ" write "v ≠ Λ", "|v| ≠ 0", "|v| > 0", or "|v| ≥ 1".
In grading the midterms and talking to students during office hours, I found some common misconceptions, which I will try to clear up.
- Many students do not seem to know the difference between
{(x,xc) : x ε Γ*} and
{(x,xc) : x ε Γ*, c ε Γ}. Let me begin with some
examples involving numbers. Unless you know the difference, please read on, regardless of how you did on the midterm.
- {n : P(n)} is the set of numbers n, such that n satisfies the condition P(n), e.g., {n : n^2 = 1} = {-1,1}.
- {2n : n ≥ 0} is the set of multiples of 2, i.e., the set of even numbers
- {10n : n ≥ 0} is the set of multiples of 10
- {cn : n ≥ 0} is the set of multiples of c. Note that this depends on c.
- {cn : n ≥ 0, c ≥ 0} = the set of natural numbers, i.e., {n : n >= 0}. Note that this does not depend on c.
- {(x,xc) : x ε Γ*} = POPc. Note that this depends on c.
- {(x,xc) : x ε Γ*, c ε Γ} = POPa U POPb. Note that this does not depend on c.
- Some students tried to use the converse of closure properties. Let τ be a finite transduction. If you prove that Lτ is regular, that doesn't prove anything about L.
- Others used properties that aren't closure properties at all: For example, {aibi} is finite, hence regular. However
Ui ≥ 0{aibi} = {aibi : i ≥ 0} , which is not regular. The class of regular languages is not closed under infinite union. - When using the pumping theorem, you must make sure that z belongs to L.
- {a*} = {{a^n : n ≥ 0}}, which is a set of languages, not a language.
- Closure properties apply to classes of languages, not individual languages. Examples: When we say that the class of regular languages is closed under union, we don't mean that each individual language is closed under union (that wouldn't even make sense, because you can't take the union of two strings). When we say that the class of regular languages is closed under concatenation, we don't mean that each individual regular language is closed under concatenation (the regular language a*b* is not closed under concatenation because it contains ab but not abab).
- To prove that two strings x and y are not prefix equivalent L, you must find a single string u such that
- xu is in L and yu is not in L, or
- xu is not in L and yu is in L
- {aibj : i-j = 5} ≠ {aibj : i ≠ j}.
- uviw ≠ z, unless i=1
- A: 144 (80%) or higher
- B: 108 (60%) or higher
- C: 72 (40%) or higher
- F: below 72
- If you don't have Java, you'll need to
download java
directly from Sun
- You can also
download JFLAP in convenient zip format
- You'll need winzip in order to open the JFLAP package.
- Strings don't commute!
- dog ≠ god
- aabb ≠ abab
- if n ≥ 2, anbn ≠ (ab)n
- A nondeterministic acceptor for L must not accept any strings that do not belong to L.
- sets
- lists and strings
- functions and relations (including transitive closure)
- arithmetic congruences (mod)
- logic, including quantifiers
- proof methods
- strong induction
In previous years, some groups would divide up the problems as soon as they were assigned and staple the solutions together the day they were due. Students in those groups didn't learn much and ended up doing poorly on the quizzes and exams.
- Homework: 10%
- Quizzes: 30%
- Midterms: 15%
- Final: 45%