CS 3531 - Theory of Automata and Formal Languages (Fall 2023)
Course Description
Introduction to the theory of computation. Deterministic and nondeterministic finite automata, regular languages and regular expressions. Kleene's Theorem. Context-free languages, context-free grammars and pushdown automata. Turing machines and computability.
Instructor
Dr. Andrew M. Sutton
Email: amsutton@d.umn.edu
Tel: 218.726.7978
Office: 311 Heller Hall
Office Hours: MWF 10:00-11:00
Teaching Assistant
José Oliveira
Email: deoli036@d.umn.edu
Office: 187 MWAH
Office Hours: MW 09:00-11:00, 16:00-17:00
Meeting Times and Locations
| Monday | 11:00 - 11:50 | M W Alworth Hall 191 |
| Tuesday | 10:00 - 10:50 | M W Alworth Hall 191 |
| Wednesday | 11:00 - 11:50 | M W Alworth Hall 191 |
| Friday | 11:00 - 11:50 | M W Alworth Hall 191 |
Pre-requisites
- CS 2531 - Discrete Structures or Math 3355 - Discrete Math
Required Textbook
Introduction to the Theory of Computation by Michael Sipser. Any edition is acceptable. It is important that you have access to the textbook because the instructor will only provide notes on material not covered by the book.
Student Learning Outcomes
- Identify different formal language classes and their relationships
- Learn and use structural induction
- Work with models of computing and understand their different powers
- Understand and formulate regular expressions
- Understand and formulate context-free grammars
- Be familiar with Turing machines and computability
Assessment Components
- Homework (30%)
- There will be a homework assignment roughly every week. Each week's assignment will be distributed on Monday and due in class at the beginning of the following Monday's class. Late homework will be deducted 20% and accepted until the beginning of Tuesday's class. Homework will not be accepted more than 24 hours late. This will allow an in-class discussion of homework solutions.
- Quizzes (10%)
- We will periodically have in-class quizzes. Each quiz will give you a chance to demonstrate what you have learned and what concepts are still hazy. Another goal of the quizzes is to encourage participation. Therefore, we will not announce quizzes ahead of time. Furthermore, we will usually go over the quiz together immediately afterwards. Because of this, we will not have make-up quizzes. However, to get you out of unforeseen circumstances, I will automatically drop the two lowest quiz scores.
- Midterm Examinations (30%)
- There will be two midterm examinations, in approximately weeks five and ten of the course. The dates of the midterms will be announced at least one week beforehand.
- Cumulative Final Examination (30%)
- The final exam will take place during finals week. The date and time will be announced beforehand. Please confirm the time before the exam, as the schedule may change. The final exam policy can be found here.
Timetable
Below is a tentative timetable for the semester.
| Week | Topic | Reading |
|---|---|---|
| 1 | Introduction, background and review of material from CS 2531 | Syllabus |
| 2 | Regular languages and finite automata | 1.1 and 1.2 |
| 3 | Regular Expressions | 1.3 |
| 4 | Nonregular languages and the pumping lemma | 1.4 |
| 5 | Wrap up of regular languages, review, Midterm Exam 1 | |
| 6 | Context-free grammars | 2.1 |
| 7 | Chomsky normal form | 2.1 |
| 8 | Pushdown automata | 2.2 |
| 9 | Non-context free languages and the pumping lemma | 2.3 |
| 10 | Wrap up context free languages, review, Midterm Exam 2 | |
| 11 | Turing machines | 3.1 and 3.2 |
| 12 | Decidability | 4.1 |
| 13 | Undecidability | 4.2 |
| 14 | Reducibility | Chapter 5 |
| 15 | Wrap up computability theory, review | |
| 16 | Final Exam |
There will be two midterms, each worth 15% of the course grade, and a cumulative final exam worth 30% of the final grade. Exams are closed-book and closed-notes. No electronic devices will be allowed. Exams will not be given early, and makeups must be justified by dire circumstances described to the instructor before the time of the exam. It is departmental policy not to return final exams. However, they will be filed in the instructor's office, and you may request to see them.
| Exam | Material | Date |
|---|---|---|
| Midterm 1 | Chapter 1 | Tuesday, October 3 |
| Midterm 2 | Chapter 2, 2.1-2.3 | Wednesday, November 8 |
| Final | Chapters 1-5 | Wedensday, December 13 (10:00am) |
Course Management System
Grades and some course documents, such as an up-to-date copy of this syllabus and a schedule updated weekly, will be available through Canvas. There will not be comprehensive course notes or slides available on Canvas. For this reason, students should have the textbook and take notes during lectures.
Class Policies
Group Work: All work submitted on homework and exams must be entirely your own. Group work is valuable for learning, and working on homework assignments in groups is encouraged, but you must write and understand your own individual solutions. You are welcome to work on the homework assignments in groups, but you should write your solutions alone to be sure that you understand them. You must be able to explain all your submitted solutions to the professor or the TA if asked. If you are unable to complete homework assignments on your own, you will have difficulty succeeding on the exams.
Extra Credit: There is no extra credit work available beyond that listed in the syllabus and course calendar.
Cheating: Academic dishonesty is taken seriously by the University. Cheating on assignments or exams, plagiarizing, or any other act which violates the rights of another student in academic work or that involves misrepresentation of your own work may result in a grade reduction on the assignment/quiz/test or a grade reduction in the class (including the possibility of failing the class).
Note that ``outsourcing'' homework effort by posting problems on
platforms such as chegg.com is a clear case of academic dishonesty! If
you are struggling with the material, contact the instructor or TA
instead.
If a student is found responsible for academic dishonesty, a report is filed with the UMD student academic integrity officer and is considered a violation of the Student Conduct Code. The UMD Student Academic Integrity Policy can be found at http://www.d.umn.edu/academic-affairs/academic-policies/classroom-policies/student-academic-integrity. The policy outlines what is considered prohibited conduct.
University Policies
Student Conduct Code
Appropriate classroom conduct promotes an environment of academic achievement and integrity. Disruptive classroom behavior that substantially or repeatedly interrupts either the instructor's ability to teach, or student learning, is prohibited. Students are expected to adhere to the Board of Regents Policy.
Student Academic Integrity
Academic dishonesty tarnishes UMD’s reputation and discredits the accomplishments of students. Academic dishonesty is regarded as a serious offense by all members of the academic community.
Appropriate Use of Class Notes & Course Materials
Taking notes is a means of recording information but more importantly of personally absorbing and integrating the educational experience. However, broadly disseminating class notes beyond the classroom community or accepting compensation for taking and distributing classroom notes undermines instructor interests in their intellectual work product while not substantially furthering instructor and student interests in effective learning.
Excused Absences
Students are expected to attend all scheduled class meetings. It is the responsibility of students to plan their schedules to avoid excessive conflict with course requirements. However, there are legitimate circumstances that lead to excused student absence from the classroom. These are subpoenas, jury duty, military duty, religious observances, illness, bereavement, and NCAA varsity intercollegiate athletics.
Final Examinations
All 1xxx-5xxx courses offered for undergraduate credit should include a final graded component or end of term evaluation that assesses the level of student achievement of one or more course objectives. All final graded components are to be administered or due at the time and place according to the final exam schedule and not during the last week of class.
Teaching & Learning: Instructor & Student Responsibilities
UMD is committed to providing a positive, safe, and inclusive place for all who study and work here. Instructors and students have mutual responsibility to ensure that the environment in all of these settings supports teaching and learning, is respectful of the rights and freedoms of all members, and promotes a civil and open exchange of ideas.
Sexual Harassment, Sexual Assault, Stalking and Relationship Violence
Sexual harassment means unwelcome sexual advances, requests for sexual favors, and/or other verbal or physical conduct of a sexual nature. Such conduct has the purpose or effect of unreasonably interfering with an individual's work or academic performance or creating an intimidating, hostile, or offensive working or academic environment in any University activity or program. Such behavior is not acceptable in the University setting. See also: Board of Regents Policy.
Equity, Diversity, Equal Employment Opportunity, and Affirmative Action
The University provides equal access to and opportunity in its programs and facilities, without regard to race, color, creed, religion, national origin, gender, age, marital status, disability, public assistance status, veteran status, sexual orientation, gender identity, or gender expression. Equal Opportunity and Affirmative Action and the Office of Student Conduct & Conflict Resolution are both available to all UMD employees, students, and participants in University-related activities to discuss issues or concerns regarding University policies or practices involving potential bias, discrimination, harassment or retaliation that an individual may have experienced or observed.
Academic Freedom and Responsibility
Thoughtful dialog is a cornerstone of higher education. This expectation is upheld in the University of Minnesota's Board of Regents Policy: Academic Freedom and Responsibility, which says in part:
SECTION II. ACADEMIC FREEDOM. Academic freedom is the freedom, without institutional discipline or restraint, to discuss all relevant matters in the classroom, to explore all avenues of scholarship, research, and creative expression, and to speak or write on matters of public concern as well as on matters related to professional duties and the functioning of the University.
Resources for Students with Disabilities
It is the policy and practice of the University of Minnesota Duluth to create inclusive learning environments for all students, including students with disabilities. If there are aspects of this course that result in barriers to your inclusion or your ability to meet course requirements such as time limited exams, inaccessible web content, or the use of non-captioned videos, please notify the instructor as soon as possible. You are also encouraged to contact the Office of Disability Resources to discuss and arrange reasonable accommodations. Call 218-726-6130 or visit the Disability Resources website for more information.
The instructor reserves the right to make changes to this syllabus or the course calendar at any time, and without prior notice.