15453 Formal Languages, Automata, and Computation  15453 Assignments, Exams and Solutions
 Homework is generally assigned on Thursday and due one week later.
 Please read all questions on an assignment soon after it is assigned. If a question is unclear, please email the TAs. Clarifications may also be posted on this Assignments page of the course website.
 Staple all your pages together.
 Do not print your assignment as white text on a black background!
 Hints for difficult problems may be posted here on this page.
Assignment  Date Assigned  Date Due  Homework 1 [pdf] [tex] Exercise 1.5b: It appears that this exercise is defective in that a straightforward solution to Exercise 1.4c also satisifies this exercise. If this is the case for your answer to Exercise 1.4c, you may simply write "Same as DFA from Exercise 1.4c" as your answer. Solutions:flachw1soln.pdf (solutions to all problems except 1.25), flachw125.soln.txt.  Thu Jan 15  Thu Jan 22  Homework 2 [pdf] [tex]
 Exercise 2 had a bug in it. The PDF file has been updated and corrected.
 For Exercise 4: Assume that language A is a regular language. This has now been clarified on the PDF file.
 Another solution to the Extra Credit problem of Assignment 1, based on the method discussed in class, is now posted: bonussoln.pdf. This solution might be helpful for Exercise 4.
Solutions: solnhw2.pdf (Notes on grading)  Thu Jan 22  Thu Jan 29  Homework 3 [flachw3.pdf  flachw3.tex]
 For Problem 1, you don't need to explicitly give a DFA; it would suffice to give an NFA and say something like "This NFA can be converted to a DFA using the standard construction".
Solutions: Ex. 13, Ex. 4  Thu Jan 29  Thu Feb 5  Homework 4 [flachw4.pdf  flachw4.tex]  Due date is now Friday by 3:30 pm (4:00 pm at the absolute latest). Turn your homework in to Denny in Wean 7116. If Denny is not there, you may slide your homework under his door.
 Note: If we decide to post hints for the problems, they will be posted here on the assignments page.
 See the announcements on the main page.
 Nerode Handout[tex]
 Solutions:pdf
 Thu Feb 5  Fri Feb 13, to Denny (Wean 7116) by 3:30 pm (4:00 at the absolute latest)  Homework 5 [flachw5.pdf  flachw5.tex]  The symbol "⊕" (circled plus) denotes the XOR function.
 For Exercise 2, you may assume that the tape has a "#" symbol before the left end and before the right end (like the example that we did in class) so that the automaton can identify when it would fall off an end of the tape.
 BDD lecture notes: bddlecture.pdf
 Solution: pdf
 Thu Feb 12  Thu Feb 19  Homework 6 [flachw6.pdf  flachw6.tex]  For Exercise 2(d) and 2(e), assume that the alphabet is {0, 1}.
For Exercise 2(f), assume that the alphabet is {0, 1, #}.  The language of Exercise 1(f) is the empty set. The notation on the original printed copy of the assignment may have been confusing.
 For Exercise 4, the constraint on m was accidentally omitted. The language should be:
{0^{n}1^{m}0^{n}1^{m}  n ≥ 0 and m ≥ 0}.  For Exercise 3, you may use the fact that a language is contextfree iff it is recognized by a pushdown automaton. Hint: Remember how we showed that the intersection of two regular languages is regular? Try a similar construction, using a PDA for the contextfree language C and a DFA for the regular language
 Solutions:Prob 1,3,4,5,6, Prob 2
 Thu Feb 19  Thu Feb 26  Midterm Exam is Tuesday March 3. Some topics you should be familiar with: Show that a given language is or is not regular.
 Given a regular language, specified like {w  foo(w)}, show how to construct an automaton that recognizes it.
 Convert an NFA to a DFA.
 Given a regular expression, construct an automaton that recognizes it.
 Given an automaton, construct an automaton that recognizes it.
 Given a DFA, find the equivalent minimal DFA.
 Given two DFAs, determine whether they are equivalent.
 Given a contextfree language, specified like {w  foo(w)}, show how to construct a pushdown automaton that recognizes it.
 Given a simple contextfree grammar (CFG), find an equivalent CFG in Chomsky normal form.
 Show that a given language is or is not contextfree, such as by using the pumping lemma for contextfree languages.
Some practice problems in your textbook (with answers in the book) for chapter 2:  Prob 2.3(f)  2.3(o).
 Prob 2.6(a) and (c).
 Homework 7 [flachw7.pdf  flachw7.tex]
 Thu Mar 19  Thu Mar 26  Homework 8 [flachw8.pdf  flachw8.tex]  Homework 8 has now been posted.
 The due date for the Bonus Problem of Homework 7 has been extended until Thursday Apr 2.
 For Problem 3, the proof regarding recursively enumerable languages is Theorem 3.21 in the textbook, on page 153.
 For Problem 3, you should assume that the language contains at least one string.
 Solution
 Thu Mar 26  Thu Apr 2  Homework 9 [flachw9.pdf  flachw9.tex]
 Thu Apr 2  Thu Apr 9  Homework 10 [flachw10.pdf  flachw10.tex]  Handout on Cook's Theorem
 There is no class on the posted due date (Spring Carnival). You may turn in your homework on the Tuesday after the posted due date (April 21) without penalty. We will not accept Homework 10 more than a week late (i.e. any later than Thursday April 23) (except in exceptional circumstances).
 Solution: pdf
 Thu Apr 9  Thu Apr 16 (no class), extended to Tuesday April 21  Homework 11 [flachw11.pdf  flachw11.tex]  Hint for exercise 7.23a (CNF SAT problems in which each variable occurs at most twice): Consider resolution: (∃x. (x ∧ A) ∨ (¬x ∧ B)) = (A ∨ B).
 Hint for exercise 7.12 (modular exponentiation): Wikipedia article.
 Solution: pdf
 Thu Apr 16  Thu Apr 23  Homework 12: Sudoku Project [flacproj.pdf  flacproj.tex] Old announcements:  Encoding Slides: ppt. Handout (pdf)
 Benchmarks: bench.zip
 Python would be a good language in which to write this program. If you're feeling adventurous and don't currently know Python, you can quickly learn enough of it in a couple of hours. Tutorial: www.python.org/doc/2.5.2/tut, debugger.
 We will test your program on 9x9 and possibly 16x16 Sudoku puzzles. Your program does not need to handle any larger puzzles.
 Program skeleton in C++ and Python, and test script: sudokuskel.zip.
 More benchmarks: morebench1.zip. (Update: benchmark files have been corrected to use spaces instead of tabs.)
 Please make sure to put your name at or near the top of your source code file.
 We will compare your output solution to the benchmark solution using "diff B w", not "diff B b". (Apparently "b" does not ignore whitespace added to the beginning of lines.)
 C++ reference on the vector STL: http://www.cplusplus.com/reference/stl/vector/. (In particular, you can use normal array indexing syntax, like “board[r][c] = d”.)
New announcements:  If you're using C/C++ and you use the sqrt function in math.h, then you may need to compile/link with the "lm" argument to link with the math library.
 If there was an error with your solver and you wish to resubmit, please upload your new file to your flacproj AFS directory and email the TAs.
Grading and Submission
Grading:  If your solver gives correct output for all the provided benchmarks and for our secret test benchmarks, you will receive an A of some sort.
 If your solver gives correct output for all the provided benchmarks, but fails one of our secret benchmarks due to a minor mistake, you will receive no lower than a B.
 If your solver gives incorrect output for the provided benchmarks, or if it fails to compile on the Andrew machines, you will receive no higher than C.
 If your program has a minor mistake, we will let you correct it and resubmit.
 In addition to automated testing, we will also briefly inspect your source code. Your code should readable by the TAs.
 Your program should display correctly for both a tabsize of 4 and a tabsize of 8. If you mix spaces and tabs for indentation in such a way that your program displays incorrectly, you may lose points.
 Your program does not need to commented, as long as it is reasonably clear what your code is doing. If you used the sample program skeleton, you probably don't need to add any comments if your program is otherwise wellwritten. If you started from scratch, a handful of highlevel comments (similar to the ones in the provided skeleton) would be helpful although not strictly necessary if your program is readily understandable without them.
Submission: Create a directory named "flacproj" in your AFS home directory, and create a subdirectory named "grading" inside it. For AFS permissions, give read permission on the flacproj directory to Will Klieber and Yi Wu, and give write permission on the grading directory. (Make sure no one else has read permission except yourself.) On the Andrew machines, you can do this by copying and pasting the following to the shell: cd ~ mkdir flacproj fs setacl flacproj wklieber read yiwu read `whoami` all clear mkdir flacproj/grading fs setacl flacproj/grading wklieber write yiwu write `whoami` all clear Put your solver source code in the flacproj directory. Your solver should named "solver.c", "solver.cpp", "solver.java", "solver.py", "solver.ml", or "solver.rb". We will use a script to automatically process your submission. If you're using C, we will compile as follows: gcc solver.c fpermissive lm o solver If you're using C++, we will compile as follows: g++ solver.cpp fpermissive lm o solver If you're using Java, we will compile as follows: javac solver.java  Tue Apr 21  Fri May 1 at 12:00 noon  FINAL EXAM. Announcements regarding the final exam will be posted here.  The exam is on Tuesday, May 5, 5:308:30 PM, in Baker Hall 136A.
 The exam will cover mostly material after the midterm exam, although you are still responsible for knowing the material from the first half of the course.
 The final exam will have a mix of proofs/problems (like on the midterm exam) and shortanswer questions.
Some possible topics:  Material from the first half of the course.
 Chapter 3 of the textbook.
 Among other things, you should be able to give a lowlevel implementation description of a Turing machine to decide a given problem.
 Chapter 4 of the textbook.
 You should definitely be able to prove that the Halting Problem is undecidable.
 Chapter 5 of the textbook.
 Chapter 7 of the textbook.
 Handout on Cook's Theorem (from April 9).
 Propositional logic. (See slides posted on April 21.)
 SAT Solvers.
 Tseitin encoding. Some notes: www.cs.cmu.edu/~ggordon/780/slides/01intro+logicannotated.pdf (starting on slide 72).
 DPLL algorithm. (You should have an intuitive sense of how it works; it's a very simple algorithm. You don't need to be familiar with the pseudocode in the GRASP slides.)
 Nonchronological backtracking.
 Implication graphs.
 Learning of new (but logically redundant) clauses. (Skip slides 23 and 24, titled "Learning (some math)"; the notation is more confusing than it is helpful.)


Leave a Comment
(0 Comments)