CS 3350 Automata, Computability, and Formal Languages
Spring 2020 Syllabus

Class Time: Tuesdays and Thursdays 9-10:20 am, LART 106

Prerequisites:

Instructor: Vladik Kreinovich, email vladik@utep.edu, office CCSB 3.0404,
office phone (915) 747-6951.

Teaching Assistant (TA): Namrata Sharma, email nsharma3@miners.utep.edu, office hours Mondays and Wednesdays 10-12 pm in CCSB 1.0706, or by appointment.

Instructor of another section of Automata: Luc Longpre, email longpre@utep.edu, office hours Mondays and Wednesdays 3-4 pm or by appointments; go to https://www.utep.edu/cs/people/longpre.html, select "Student appointments" for instructions on how to make appointments at other times.

Course Objectives: Theoretical computing models and the formal languages they characterize: Finite state machines, regular expressions, pushdown automata, context-free grammars, Turing machines and computability. Capabilities and limitations of each model, and applications including lexical analysis and parsing.

Major Topics Covered in the Course

Learning Outcomes

Level 1: Knowledge and Comprehension
Level 1 outcomes are those in which the student has been exposed to the terms and concepts at a basic level and can supply basic definitions. The material has been presented only at a
superficial level.
Upon successful completion of this course, students will be able to:

1a. Describe implications of Church-Turing thesis.

1b. Describe problems for which an algorithm exists, and problems for which there are no algorithms (non-recursive, non-recursively enumerable languages) and describe the implications of such results.

1c. Describe and explain the diagonalization process as used in proofs about computability.

1d. Describe the difference between feasible and non-feasible algorithms, describe the limitations of the current formalization of feasibility as polynomial-time.

1e. Describe the main ideas behind the concepts of NP and NP-hardness, know examples of NP-hard problems.

Level 2: Application and Analysis
Level 2 outcomes are those in which the student can apply the material in familiar situations, e.g., can work a problem of familiar structure with minor changes in the details.
Upon successful completion of this course, students will be able to:

2a. Convert a non-deterministic FA (respectively transition graph) into an equivalent deterministic FA.

2b. Convert a transition graph or NFA into an equivalent regular expression.

2c. Convert a regular expression into an equivalent FA.

2d. Construct a regular expression (respectively a context-free grammar) for a regular language (respectively context-free language).

2e. Convert a context-free grammar into an equivalent pushdown automaton.

2f. Construct a context-free grammar for a given context-free language.

2f. Design an algorithm for a machine model to simulate another model.

2h. Build simple Turing machines.

2i. Prove formally properties of languages or computational models.

2j. Apply a parsing algorithm.

2k. Build a parse tree or a derivation from a context-free grammar.

2l. Use the closure properties in arguments about languages.

Level 3: Synthesis and Evaluation
Level 3 outcomes are those in which the student can apply the material in new situations. This is the highest level of mastery.
Upon successful completion of this course, students will be able to:

3a. Compare regular, context-free, recursive, and recursively enumerable languages.

3b. Compare FA, PDA, and Turing machines.

Textbook: Reading and laboratory assignments will be drawn from Introduction to the Theory of Computation, by Michael Sipser (both 2nd and 3rd editions are OK). This book is available at the bookstore and through major online book retailers, and you are expected to acquire a copy for your use in this course. Photocopied textbooks are illegal and their use will not be tolerated.

Assignments: Reading and homework assignments will be handed out or announced in class and in labs. If you miss a class, it is your responsibility to find out what you missed. You should expect to spend at least 10 hours/week outside of class on reading and homework.

Exams: There will be three tests, on February 20, March 24, and April 30, and the final exam on May 12, 10 am - 12:45 pm.

The purpose of the exams is to allow you to demonstrate mastery of course concepts. Make-up exams will be given only in extremely unusual circumstances. If you must miss an exam, please meet with an instructor, BEFORE the exam if at all possible.

Grading: Each topic means home assignments (mainly on the sheets of paper, but some on the real computer). Maximum number of points:

The nominal percentage-score-to-letter-grade conversion is as follows:

We reserve the right to adjust these criteria downward, e.g., so that 88% or higher represents an A, based on overall class performance. The criteria will not be adjusted upward, however.

Homework Assignments: Homework and lab assignments are designed to allow you to practice using the concepts presented in lecture and in your reading. Homework and lab assignments may include written problems, tutorial exercises, and programming problems. Assignments usually will be due at the start of the next class. Late homework will be accepted only in unusual circumstances, by prior arrangement if at all possible.

Homework must be done individually. While you may discuss the problem in general terms with other people, your answers and your code should be written and tested by you alone. If you need help, consult a TA or a professors

Quizzes: The purpose of a quiz is to ensure that you have read the weekly reading assignment and to verify that you have mastered the major concepts of recent lectures. Quizzes typically will be about 5-10 minutes in length and will cover the material assigned to be read for the upcoming lecture plus selected concepts from previous lectures. There will be no make-up on missed quizzes.

Special Accommodations: If you have a disability and need classroom accommodations, please contact the Center for Accommodations and Support Services (CASS) at 747-5148 or by email to cass@utep.edu, or visit their office located in UTEP Union East, Room 106. For additional information, please visit the CASS website at http://www.sa.utep.edu/cass. CASS's staff are the only individuals who can validate and if need be, authorize accommodations for students.

Scholastic Dishonesty: Any student who commits an act of scholastic dishonesty is subject to discipline. Scholastic dishonesty includes, but not limited to cheating, plagiarism, collusion, submission for credit of any work or materials that are attributable to another person.

Cheating is:

Plagiarism is: To avoid plagiarism see: https://www.utep.edu/student-affairs/osccr/_Files/docs/Avoiding-Plagiarism.pdf

Collusion is unauthorized collaboration with another person in preparing academic assignments.

Instructors are required to -- and will -- report academic dishonesty and any other violation of the Standards of Conduct to the Dean of Students.

NOTE: When in doubt on any of the above, please contact your instructor to check if you are following authorized procedure.

Daily Schedule: (tentative and subject to change)

January 21: topics to cover:

assignments:

January 23: topics to cover:

January 28: topics to cover: assignments:

January 30: topics to cover:

February 4: topics to cover:

assignment:

February 6: topics to cover:

February 11: topics to cover:

assignments:

February 13: topics to cover:

February 18: overview for Test 1 (cont-d).

assignments:

February 20: Test 1 that covers all the material that we have studied so far.

February 25: topics to cover:

assignments:

February 27: topics to cover:

March 3: topics to cover: assignments:

March 5: topics to cover:

March 10: topics to cover:

assignments:

March 12: preview for Test 2

March 31: Test 2

April 2: see lecture; topics to cover:

April 7: topics to cover:

assignments:

April 9: see Section 2.1.1 of a handout; topics to cover:

April 14: see lecture and Sections 2.2 and 2.3 of the handout; topics to cover:

assignments:

April 16: see lecture; topics to cover:

assignments:

April 21: see lecture; topics to cover:

April 23: see the lecture; topics to cover:

assignment: reproduce the proof of the halting problem in all the necessary detail.

April 28: preview for Test 3

April 30: Test 3.

May 5: overview of Test 3 results, preview for final exam.

May 7: see the lecture; topics to cover: