# Pushdown Automata Homework Examples For Students

## CS 181 Languages and Automata

Quarter | Spring 2015 | |

Instructor | Prof. Alexander Sherstov | |

TAs | David Felber, Zhinan Guan, Xin Zhang | |

Lecture | MW 2–3:50pm (BOELTER 3400, instructor) | |

Discussion (1A) | F 2–3:50pm (PUB AFF 2214, David) | |

Discussion (1B) | F 4–5:50pm (PUB AFF 2214, Xin) | |

Discussion (1C) | F 4–5:50pm (PUB AFF 1337, Zhinan) | |

Webpage | http://www.cs.ucla.edu/~sherstov/teaching/2015-spring | |

Textbook | M. Sipser, Introduction to the Theory of Computation, 3rd ed., 2012 | |

Office Hours | MW 1:30–2pm (BOELTER 3731J, instructor) | |

MTWR 11–12noon (BOELTER 2432, David) | ||

MW 12–1pm, TR 1–2pm (BOELTER 2432, Xin) | ||

F 11–12noon (BOELTER 2432, Zhinan) |

“Everything should be made as simple as possible, but not simpler.

Albert Einstein

## Description

This course is an undergraduate introduction to the theory of computation. We will study a variety of abstract computational devices, from very simple and limited to highly sophisticated and powerful: deterministic and nondeterministic finite automata, regular expressions, pushdown automata, context-free grammars, and Turing machines. We will completely characterize the relative computational capabilities of these devices. Lastly, we will discover that there are important practical problems that cannot be solved by any computational device at all.

This is a rigorous course with an emphasis on mathematical proofs. Please do not enroll if you have not taken the prerequisites, which are CS 32 "Introduction to Computer Science II" and one of MATH 61 "Introduction to Discrete Structures," MATH 180 "Combinatorics."

## Grading

*Homework (10 x 2%).* There will be ten weekly homework assignments, each worth 2% of your course grade. Homework will be graded based primarily on effort rather than correctness, using the following grading scheme: 2% for a good-faith effort (more than half of the problems attempted), 1% for some effort (less than half of the problems attempted), and 0% for unintelligible, late, or unsubmitted homework. Homework assignments will be posted on the course webpage by 4pm on Mondays, including official holidays. Please submit your homework by 1:59pm on Friday of the same week, using the corresponding TA drop box in 2432 Boelter Hall: Box A1, Box A2, and Box A3 for discussion section 1A, 1B, and 1C, respectively. Homework solutions will be worked out on the blackboard in the discussion sections. Please feel free to collaborate with other students on the homework or use any outside scholarly sources. However, you must write up your solutions on your own and indicate with whom you have collaborated. If you have worked on your own, you must state that as well.

*Exams (4 x 20%).* There will be three exams during the quarter (April 24, May 8, and May 22) and an additional final exam (June 8). The exams are closed-book and closed-notes. The first three exams will be administered in the discussion sections; please attend the exact discussion section in which you are enrolled. Exam solutions will be posted on the course webpage by the end of the day on the exam date. No alternate or make-up exams will be administered, except for disability/medical reasons documented and communicated to the instructor prior to the exam date. In particular, exam dates and times cannot be changed to accommodate scheduling conflicts with other classes.

## Course Schedule

The following table gives the sequence of topics that we will cover, along with the number of hours of instruction devoted to each topic and the corresponding chapters of the Sipser textbook.

Here is a more detailed view, with the primary topic indicated for each lecture date. The color coding shows the primary scope for each of the four exams.

## Homework

The problem numbers below refer to the Sipser textbook.

Week | Assignment | |

1 | 1.1, 1.6 (b, d, e, f, h, j, k, n) | |

2 | Download | |

3 | 1.16, 1.32, 1.40, 1.41, 1.62, 1.66(a), 1.69 | |

4 | 1.21, 1.28, 1.47, 1.49, 1.53 | |

5 | Download | |

6 | 2.1, 2.6(d), 2.19, 2.27, 2.28(c) | |

7 | 2.11, 2.20, 2.30(a,d), 2.45 | |

8 | 3.1, 3.5, 3.8(b), 3.16(a-d) | |

9 | 3.10, 3.12, 3.13, 3.16(e), 3.20 | |

10 | 3.7, 4.12, 4.14, 4.17, 4.27 |

## Weekly Planner

## Practice Exams

The practice exams below are from previous offerings of this course and are representative of what you should expect this quarter. There are several samples for each exam, with solutions included at the end of every sample.

### Exam 1

Sample 1 | |

Sample 2 |

### Exam 2

Sample 1 | |

Sample 2 |

### Exam 3

Sample 1 | |

Sample 2 |

### Final Exam

Sample |

## Exam Solutions

The problems on the midterm and final exams are selected from the following textbooks on the theory of computing: *Theory of Computing: A Gentle Introduction* by E. Kinber and C. Smith, *Elements of the Theory of Computation* by H. Lewis and C. H. Papadimitriou, *Introduction to Languages and the Theory of Computation* by J. Martin, and *Introduction to the Theory of Computation* by M. Sipser.

## Policies

*Attendance and class participation.* Although not a formal component of the course grade, attendance is essential for success in this course. If you are absent without a documented excuse, the instructor and TAs will not be able to go over missed lecture material with you. We emphatically welcome questions and any other input from you—your active participation in this course will enhance your learning experience and that of the other students.

*Academic honesty.* The students are expected to fully abide by UCLA's student conduct policies, including Section 102.01 on academic honesty. You will find a wealth of helpful materials here, including the Student Guide to Academic Integrity. Academic dishonesty will be promptly reported to the Dean of Students' Office for adjudication and disciplinary action. Remember, cheating will have significant and irrevocable consequences for your academic record and professional future. Please don't cheat.

*Regrade requests.* Regrade requests for homework and exams must be made within one week after the graded assignments have been handed out, regardless of your attendance on that day and regardless of any intervening holidays such as Memorial Day. Please put your request in writing, indicating the parts you want regraded and why, and hand in your request in person to a TA.

*Late arrival to an exam.* Students arriving 15 minutes late will not be admitted to the exam and will automatically receive a score of 0. This policy applies to all four exams.

*Record keeping.* Students are expected to monitor their posted homework/exam scores in Gradebook throughout the quarter and bring up any inaccuracies in a timely manner, no later than 7 days of the date the scores were posted. All scores will be considered final at 5pm on Friday of Finals Week, with no further changes or corrections possible.

## CS 181 Languages and Automata

Quarter | Fall 2016 | |

Instructor | Prof. Alexander Sherstov | |

TAs | Yunzhong He, Pei Wu | |

Lecture | MW 2–3:50pm (BOELTER 5249, instructor) | |

Discussion A | F 12noon–1:50pm (HAINES A18, Pei) | |

Discussion B | F 2–3:50pm (HUMANTS 169, Yunzhong) | |

Webpage | http://www.cs.ucla.edu/~sherstov/teaching/2016-fall | |

Textbook | M. Sipser, Introduction to the Theory of Computation, 3rd ed., 2012 | |

Office Hours | MW 1:30–2pm (BOELTER 3731J, instructor) | |

MW 11:00am–1:00pm (BOELTER 2432, Yunzhong) | ||

TR 10:30–12:30 (BOELTER 2432, Pei) | ||

F 10:50–11:50 (BOELTER 2432, Yunzhong & Pei) |

“Everything should be made as simple as possible, but not simpler.

Albert Einstein

## Description

This course is an undergraduate introduction to the theory of computation. We will study a variety of abstract computational devices, from very simple and limited ones to highly sophisticated and powerful: deterministic and nondeterministic finite automata, regular expressions, pushdown automata, context-free grammars, and Turing machines. We will completely characterize the relative computational capabilities of these devices. Lastly, we will discover that there are important practical problems that cannot be solved by any computational device at all!

This is a rigorous course with an emphasis on mathematical proofs. Please do not enroll if you have not taken the prerequisites, which are CS 32 "Introduction to Computer Science II" and one of MATH 61 "Introduction to Discrete Structures," MATH 180 "Combinatorics."

## Grading

*Homework (10 x 2%).* There will be ten weekly homework assignments, each worth 2% of your course grade. Homework will be graded based on effort rather than correctness, using the following grading scheme: 2% for a good-faith effort (more than half of the problems attempted), 1% for some effort (less than half of the problems attempted), and 0% for unintelligible, late, or unsubmitted homework. Homework assignments will be posted on the course webpage by 5pm on Mondays, including official holidays. Please submit your homework by 11:50am on Friday of the same week, using the corresponding TA drop box in 2432 Boelter Hall: box A1 for Pei's discussion section, and box A2 for Yunzhong's discussion section. Homework solutions will be worked out on the blackboard in discussion sections, and solutions to the more difficult problems will be uploaded in PDF format to CCLE. Please feel free to collaborate with other students on the homework or use any outside scholarly sources. However, you must write up your solutions on your own and indicate with whom you have collaborated. If you have worked on your own, you must state that as well.

*Exams (4 x 20%).* There will be three exams during the quarter (October 21, November 4, and November 18) and an additional final exam (December 5). The exams are closed-book and closed-notes. The first three exams will be administered in the discussion sections; please attend the discussion section in which you are enrolled. Exam solutions will be posted on the course webpage by the end of the day on the exam date. No alternate or make-up exams will be administered, except for disability/medical reasons documented and communicated to the instructor prior to the exam date. In particular, exam dates and times cannot be changed to accommodate scheduling conflicts with other classes.

## Course Schedule

The following table gives the sequence of topics that we will cover, along with the number of hours of instruction devoted to each topic and the corresponding chapters of the Sipser textbook.

Here is a more detailed view, with the primary topic indicated for each lecture date. The color coding shows the primary scope for each of the four exams.

## Homework

The problem numbers below refer to the Sipser textbook.

Week | Assignment | |

1 | 1.1, 1.6 (b, d, e, f, h, j, k, n) | |

2 | Download | |

3 | 1.16, 1.32, 1.40, 1.41, 1.62, 1.66(a), 1.69 | |

4 | 1.21, 1.28, 1.47, 1.49, 1.53 | |

5 | Download | |

6 | 2.1, 2.6(d), 2.19, 2.27, 2.28(c) | |

7 | 2.11, 2.20, 2.30(a,d), 2.45 | |

8 | 1.54, 1.63(a), 1.64(a-c), 2.9, 2.24, 2.31 | |

9 | 3.8(b), 3.10, 3.12, 3.13, 3.16(a-d) | |

10 | 3.20, 4.12, 4.14, 4.17, 4.27 |

## Weekly Planner

## Exams from Previous Years

Below, you will find every single exam that I have administered in my previous offerings of CS 181, complete with a solution to each problem. Work on the exams on your own under the time constraints before you study the solutions. Some problems on these exams are adapted from or inspired by the following textbooks on the theory of computing: *Theory of Computing: A Gentle Introduction* by E. Kinber and C. Smith, *Elements of the Theory of Computation* by H. Lewis and C. H. Papadimitriou, *Introduction to Languages and the Theory of Computation* by J. Martin, and *Introduction to the Theory of Computation* by M. Sipser. You can download all the exams at once as a ZIP archive for convenient offline access:

ALL EXAMS |

Alternately, or you can browse the individual exams below, grouped by quarter.

### Fall 2015

### Spring 2015

### Spring 2014 A

### Spring 2014 B&C

### Spring 2013

Midterm | Final |

## Exam Solutions

The official solutions to this quarter's exams are posted here. A problem in mathematics often has several valid solutions, so don't worry if your approach is different from the posted solutions.

## Policies

*Attendance and class participation.* Although not a formal component of the course grade, attendance is essential for success in this course. I emphatically welcome questions and any other input from you—your active participation in this course will enhance your learning experience and that of the other students.

*Academic honesty.* The students are expected to fully abide by UCLA's student conduct policies, including Section 102.01 on academic honesty. You will find a wealth of helpful materials here, including the Student Guide to Academic Integrity. Academic dishonesty will be promptly reported to the Dean of Students' Office for adjudication and disciplinary action. Remember, cheating may have significant and irrevocable consequences for your academic record and professional future. Please don't cheat.

*Regrade requests.* Regrade requests for homework and exams must be made within one week after the graded assignments have been handed out, regardless of your attendance on that day and regardless of any intervening holidays such as Memorial Day. Please put your request in writing, indicating the parts you want regraded and why, and hand in your request in person to a TA.

*Late arrival to an exam.* Students arriving 15 minutes late will not be admitted to the exam and will automatically receive a score of 0. This policy applies to all four exams.

*Record keeping.* Students are expected to monitor their posted homework/exam scores in Gradebook throughout the quarter and bring up any inaccuracies in a timely manner, no later than 7 days of the date the scores were posted. All scores will be considered final at 5pm on Friday of Finals Week, with no further changes or corrections possible.

*Email policy.* Neither the instructor nor the TAs are able to take questions about course material by email, due to the large number of enrolled students as well as the considerable chance of miscommunication. Please take advantage of the abundant office hours, class time, and discussion sections to make sure that all your questions are answered.

## 0 thoughts on “Pushdown Automata Homework Examples For Students”