15453 Formal Languages, Automata, and Computation


Main
Page




Syllabus

Assignments



Grading

Reading


Professor


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 
Thu Feb 12 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 
Thu Apr 30
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.)

