assignments
due Tue Jan 24
Week One
- Problems 0.3, 0.7, 0.11 and 0.12 from Sipser (2nd ed.)
- Show that 1.2 + 2.3 + 3.4 + ... + n(n+1) = n(n+1)(n+2)/3 for all positive integers n (where "." denotes multiplication)
due Tue Jan 31
Week Two
- Code in the language of your choice a program that implements a DFA and/or NFA. Use if possible our file input spec at finite state automata. Do enough testing on class examples or others to be sure it works as expected. You may look at other folks work, but if so state clearly what's your work and what is not.
- For each of the following two finite state machines :
- describe the states, alphabet, transition function, and whether its a DFA or NFA,
- implement with your coded machine, and try some strings,
- characterize in your own words the language accepted.
- For each of the following, draw a picture and if possible demonstrate with your code. The alphabet is [0,1] in each case.
- Provide a DFA that recognizes La = { w | w begins with 1 and ends with 0}.
- Provide a DFA that recognizes Lb = { w | w contains an even number of 0's or exactly two 1's}.
- Provide an NFA that recognizes Lc = { w | w contains 1100 or does not contain 1010}.
due Tue Feb 7
Week Three
- Read 2.1 on Context Free Grammars.
- From Sipser (2nd ed.): Do one part of your choice from each of Exercises 1.4, 1.5. 1.6 and 1.7.
- Also form Sipser: Exercises 1.14, 1.29b 1.54, 1.57 and 1.58.
- You might find it useful to keep in mind that regular languages are closed under union, intersection, concatenation, and complement (you'll show closure under complementation in Problem 1.14). Also, the result of Problem 11 might help simplify your solution to 1.57.
- Partial solutions for 1.57 and 1.58:
- For 1.57, let M be an NFA with start state q_0
and a single accept state q_a
that recognises A. The idea is simultaneously run forwards through the input string and backwards through any possible extension of that string to one in A
. Let the states of our machine be all ordered pairs of states in M. Our start state is (q_0, q_a)
and our accept states are those of the form (q,q)
. If we are in state (q_1, q_2)
and we recieve input x then we move to all states of the form (q_3,q_4)
where M moves from q_1
to q_3
when it recieves input x and M can move from q_4
to q_2
on some input (not necessarily x).
- For 1.58, consider A = a * b + c *
and think about the intersection of
with a*c*.
due Tue Feb 14
Week Four
- Read http://search.cpan.org/src/DCONWAY/Parse-RecDescent-1.94/tutorial/tutorial.html
- Write a program to parse and evaluate arithmetic like"1 + 2 * 6". The computer language and specific arithmetic grammarare up to you, but be sure to define your syntax precisely usinga grammar like the ones we're talking about. In particular,be clear about what operations are allowed, what forms numbers can take,and which operations take precedence of which others.
- There may be more coming.
due Tue Feb 21
Week Five
- Show that the class of context-free languages is closed under concatenation.
- From Sipser (2nd ed.): 2.9, 2.10, 2.31, 2.36.
- Read Chapter 3 of Sipser.
due Tue Feb 28
Week Six
- Read 4.1 of Sipser.
- From Sipser (2nd ed.): 3.8b, 3.13.
- Create a turing machine that multiplies two integers, analogous toadd.vtmmachine that adds two integers.
due Tue Mar 7
Week Seven
- From Sipser (2nd ed.): 4.7, 4.10, 4.18, 4.22.
due Tue Apr 4
Week Eight
due Tue Apr 11
Week Nine
- From Sipser (2nd ed.): 5.4, 5.14, 5.15, 5.20, 5.26
due Tue Apr 18
Week Ten
- Choose a classic P problem. Implement a computerprogram in a language of your choice that solves itfor various n, and show that the runtime is a polynomial.
- Do the same for a classic NP problem, but this timeshow that the runtime is exponential.
- Finally, demonstrate that a solution to that NP problemcan be verified by a program that runs in polynomial time.
due Tue Apr 25
Week Eleven
- Finish reading chapter
- Do 7.26 (flip cards)
- Check one of the mine-sweeper logic gates.
Final Exam
- Take home, out Fri May 5, due Mon May 8 10am
- pdf
- Use whatever sources; document and cite them clearly.
- No help from other people - ask us if there are questions.
Term Grade
