# Computation Theory Homework Solutions

## 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.

This page, http://www.cs.uiowa.edu/~hzhang/c135/, is always under construction.

## CS4330 Theory of Computation, Spring 2017

#### Prerequisite: C or better in Algorithms (CS:3330) or its equivalent

#### 11:00-12:15 TuTh, 213 E120 AJB

Makeup Lectures on March 8:

3:30-5:00pm: MLH 217

7:30-9:00pm: MLH 214

## Goals and Objectives

This course is a theoretic exploration of computing devices. Some of the questions we ask and attempt to answer are the following. Are there problems that cannot be solved on any computing device? How does one determine if a given problem can or cannot be computationally solved? If we place bounds on the resources (time and space) available to a computer, then what can be said about which problems can and which problems cannot be solved on a computer? How does the power of a computer change, if it has access to random bits?

In attempting to answer these questions we will study the following topics:

- Computation models: Finite State Automata.
- Regular Expressions and Regular Grammars.
- Context-free Grammars and Pushdown Automata.
- Computation models: Turing machines (TM).
- Turing-decidable and Turing-recognizable languages.
- Enhancements of TMs: multi-tape TMs, non-deterministic TMs. Equivalence of these and the standard TM.
- Diagonalization. Acceptance problem is undecidable; Acceptance problem is recognizable; the complement of the Acceptance problem is unrecognizable.
- Reductions. Examples of other undecidable languages. Rice's theorem. Post's Correspondence Problem (PCP) is undecidable.
- Running time of Turing Machines. The classes P, NP, NP-hard, and NP-complete.
- Cook-Levin Theorem, some reductions.
- Space complexity, Savitch's Theorem, PSPACE. Quantified boolean formula satisfiability is PSPACE-complete. So is Generalized Geography.
- The space heirarchy and the time heirarchy theorems.

### Textbook

Introduction to the Theory of Computation(third edition) by Professor Michael Sipser. The latest errata can be found at math.mit.edu/~sipser/book.html### Homeworks (10 homeworks, each counts for three percent of the final score)

LATE-DUE HOMEWORK ARE NOT ACCEPTED. In general you will be better off turning in what you have on time rather than seeking extra time to complete your work. There will be no make-up exams in general and exceptions will be rare and only for students whose reasons are included in the University's policy on "Excused Absences from Examinations".- Homework 1 (30 points) Due date: 1/31/2017

Page 83-84: 1.4 (a, c, e, f, g); 1.5 (c-g); 1.6 (a-e).

sample solution - Homework 2 (30 points) Due date: 2/9/2017

Page 84-86: 1.7 (c-e); 1.13; 1.16; 1.17; 1.18.

sample solution - Homework 3 (30 points) Due date: 2/21/2017

Page 86-93: 1.21 (alternative methods are fine); 1.28; 1.42; 1.46 (a, c); 1.71.

Page 154-156: 2.4 (b,c,e); 2.9; 2.10.

sample solution - Homework 4 (30 points) Due date: 3/2/2017

Page 155-157: 2.6 (d); 2.12; 2.13; 2.14; 2.25; 2.30 (a,d); 2.31.

sample solution - Homework 5 (30 points) Due date: 3/9/2017

Page 187-189: 3.2 (b,d); 3.8 (b,c) (describe how the tape is changed and how the head moves);3.15 (b,d); 3.16 (c,d).

sample solution - Homework 6 (30 points) Due date: 3/30/2017

Page 211-212: 4.11; 4.13; 4.17; 4.21; 4.28.

sample solution - Homework 7 (30 points) Due date: 4/6/2017

Page 239-240: 5.9; 5.12; 5.13; 5.30 (b,c).(No use of Rice's Theorem in this homework, except 5.30).

sample solution - Homework 8 (30 points) Due date: 4/13/2017

Page 240-242: 5.21; 5.23; 5.24; 5.33; 5.35.

sample solution - Homework 9 (30 points) Due date: 4/20/2017

Page 322-324: 7.7; 7.10; 7.12; 7.13; 7.18; 7.20.

sample solution - Homework 10 (90 points) Due date: 5/13/2017

Page 324-326: 7.21; 7.22; 7.24; 7.26; 7.30; 7.35.

Page 357-358: 8.3; 8.4; 8.6; 8.8.

### Exams (two midterms and one quiz, all in class time)

** The final grade is based on the final score and curved for those whose final score is at least 30% of the full final score. **

### Policies

For the policies on ACADEMIC DISHONESTY and PROCEDURE FOR COMPLAINT, see the Student Academic Handbook, http://www.clas.uiowa.edu/students/academic_handbook/index.shtml of the Colleage of Liberal Arts and Sciences. The instructor of this course will follow the policies outlined at http://www.clas.uiowa.edu/faculty/teaching/new_policytemplate.shtml for ACCOMMODATIONS FOR DISABILITIES, UNDERSTANDING SEXUAL HARASSMENT, REACTING SAFELY TO SEVERE WEATHER.

### Lecture Notes

You are expected to study all the material in each chapter covered in the class even if that material is not explicitly discussed in class or in the homework.

The lecture notes are a supplement to the course textbooks. They are supposed to help you understand the textbook material better, *they are a replacement for neither the textbook nor the lecture itself*.

Please download/print the lecture notes on the day of the class as it will be updated most likely on that day.

- 1 Introduction PDF
- 2 Regular Languages PDFpart 2 PDF
- 3 Context-free Languages PDFDPDA PDF
- 4 Turing Machines PDF
- 5 Decidability PDF
- 6 Reducibility PDF
- 7 Time Complexity PDF
- 8 NP Completeness PDF
- 9 Space Complexity PDF
- 10 Advanced Topics PDF

*Hantao Zhang*

## 0 Replies to “Computation Theory Homework Solutions”