1 Gulrajas

Homework Solutions Push Down Automata Example Problem

Homework assigned every Friday and is due the following Friday in class; No late homework excepted.
You are encouraged to work in groups to solve the homework problems, however, solutions must be written in your own words and you must fully understand everything that you submit. Students suspected of violating this will be asked to explain their homework solutions in person.
Homework is VERY important; at least half of your final grade will be based on your homework scores. Therefore it is very important that homework is done carefully and legibly. Unreadable homework will be returned and will receive no credit.


(All problems from Hopcroft, Motwani, and Ullman unless otherwise specified)

Each problem in an assignment is graded by a different TA, if you have questions about the grading, please contact to the corresponding TA.

  1. problems 1,2,3 [solutions]
  2. problems 4,5
  3. problems 6,7 [solutions]
  4. problems 8,9 [Solution]

  1. problem 1 
  2. problem 3.2.2
  3. problem 3  [Solutions]
  4. problems 4.2.1 [Solution]

  1. problem 1(4.2.1) [Solution]
  2. problem 2
  3. 4.2.6 by Machine Const. [Solution]
  4. problem 4 (4.2.6 by homomorphism, etc) [Solution]
  5. problem 5 [Solution]


Assignment #6:See Handout 

Please submit your solutions on 4 sheets of paper:

  1. problems 1,2, [Solutions]
  2. problems 3,4 [Solutions]
  3. problems 5,6 [Solution]
  4. problems 7 [Solution]

Assignment #7:

See Handout

Please submit your solutions on 4 sheets of paper: 

  1. problem 1 [Solution]
  2. problem 2[Solution], problem 3
  3. problem 4 (6.2.2b)[Solution]
  4. problem 5  [Solution]

Assignment #8:  See Handout

Please submit your solutions on 4 sheets of paper:

  1.  problems 1 [Solution], 2 [Solution]
   2.  problem 3 [Solution]
   3.  problem 4 [Solution]
   4.  problem 5 [Solution]

Assignment #9:  See Handout

Please submit your solutions on 5 sheets of paper:

   1.  problem 1 [Solution]
    2.  problem 2 [Solution]
    3.  problem 3 [Solution]
    4.  problem 4 [Solution]
    5.  problem 5 [Solution]

Assignment #10: See Handout

  1. Problem 1 [Solution]
  2. Problem 2 [Solution]
  3. Problem 3 [Solution]
  4. Problem 4

Assignment #11:  See Handout

Please submit your solutions on 4 sheets of paper:

   1.  problem 1 [See Book P. 380]
    2.  problem 2 [Solution]
    3.  problem 3 [Solution]
    4.  problem 4

Assignment #12:  See Handout

Please submit your solutions on 4 sheets of paper:

    1.  problem 1 [Solution]
    2.  problem 2  [Solution]
    3.  problem 3 [Solution]
    4.  problem 4 [Solution]

Assignment #13:  See Handout

Please submit your solutions on 4 sheets of paper:

   1.  problem 1 [See Book P.455 and 456]
    2.  problem 2 [Solution] 
    3.  problem 3  [Solution]
    4.  problem 4 [Solution]

Assignment #14:  See Handout  [Solution]

15-453 Formal Languages, Automata, and Computation

15-453 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.

AssignmentDate AssignedDate 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:flac-hw1-soln.pdf (solutions to all problems except 1.25), flac-hw1-25.soln.txt.
Thu Jan 15Thu 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: bonus-soln.pdf. This solution might be helpful for Exercise 4.
Solutions: soln-hw2.pdf (Notes on grading)
Thu Jan 22Thu Jan 29
Homework 3 [flac-hw3.pdf | flac-hw3.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. 1-3, Ex. 4
Thu Jan 29Thu Feb 5
Homework 4 [flac-hw4.pdf | flac-hw4.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 [flac-hw5.pdf | flac-hw5.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: bdd-lecture.pdf
  • Solution: pdf

Thu Feb 12Thu Feb 19
Homework 6 [flac-hw6.pdf | flac-hw6.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:
    {0n1m0n1m | n ≥ 0 and m ≥ 0}.
  • For Exercise 3, you may use the fact that a language is context-free 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 context-free language C and a DFA for the regular language
  • Solutions:Prob 1,3,4,5,6, Prob 2

Thu Feb 19Thu 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 context-free language, specified like {w | foo(w)}, show how to construct a pushdown automaton that recognizes it.
  • Given a simple context-free grammar (CFG), find an equivalent CFG in Chomsky normal form.
  • Show that a given language is or is not context-free, such as by using the pumping lemma for context-free 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 [flac-hw7.pdf | flac-hw7.tex]
Thu Mar 19Thu Mar 26
Homework 8 [flac-hw8.pdf | flac-hw8.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 26Thu Apr 2
Homework 9 [flac-hw9.pdf | flac-hw9.tex]
Thu Apr 2Thu Apr 9
Homework 10 [flac-hw10.pdf | flac-hw10.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 9Thu Apr 16 (no class), extended to Tuesday April 21
Homework 11 [flac-hw11.pdf | flac-hw11.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 16Thu Apr 23
Homework 12: Sudoku Project [flac-proj.pdf | flac-proj.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: sudoku-skel.zip.
  • More benchmarks: more-bench-1.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
  • 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 well-written. If you started from scratch, a handful of high-level 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:30-8: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 short-answer 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 low-level 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/01-intro+logic-annotated.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.)
    • Non-chronological 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


Your email address will not be published. Required fields are marked *