CS 3350 Automata, Computability, and Formal Languages
Fall 2021 Syllabus

Class Time: Tuesdays and Thursdays 12-1:20 pm

Room: CCSB 1.0202

General Prerequisites: CS 2302 "Data Structures" and either Discrete Mathematics or Discrete Structures, both with grades C or higher.

Alternative Prerequisites: CS 2401 "Elementary Data Structures and Algorithms" and either Discrete Mathematics or Discrete Structures, both with grades B or higher.

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

Preferable way of contact is by email.
  • If you want to contact the instructor during the scheduled office hours, there is no need to schedule an appointment.
  • If you cannot contact the instructor during the instructor's scheduled office hours, please schedule an appointment in the following way: He will then send a reply email, usually confirming that he is available at this time, and he will place the meeting with you on his schedule.

    Teaching Assistant (TA): Laxman Bokati, email lbokati@miners.utep.edu, office hours:

    Instructor of Another Section of Automata: Luc Longpre.

    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 for a regular 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: 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 announced on the class website. You should expect to spend at least 10 hours/week outside of class on reading and homework.

    Exams: There will be three tests: on September 23, October 21, and November 23, and the final exam on December 7, 1-3:45 pm. The logistics of each test is very straightforward:

    Similar to homeworks, I will post solution, send you the grades, and answer questions if something is not clear.

    As usual, if you are unable to attend the test, let me know, I will organize a different version of the text at a time convenient for you.

    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: Each topic means home assignments. Howeworks will be usually assigned on Tuesday and be due on Thursday, by the start of the Thursday class. To submit a homework, send it to the Teaching Assistant (TA) by email. If it is not electronic, scan it and send him/her the scanned version. If you have a legitimate reason to be late, let me and the TA know, you can then submit it until the following Tuesday. If you were simply late, you can still submit until next Tuesday, but then the TA will take off points for submitting late.

    The TA will take off points for submitting late. He/she will send you the grades. On Tuesday the next week, I will post correct solutions, and both I and the TA will be glad to answer questions if needed.

    Since I will be posting correct solutions to homeworks, it does not make any sense to accept very late assignments: once an assignment is posted, it make no sense for you to copy it in your own handwriting, this does not indicate any understanding. So, please try to submit your assignments on time.

    Things happen. If there is an emergency situation and you cannot submit it on time, let me know, you will then not be penalized -- and I will come up with a similar but different assignment that you can submit directly to me (not to the TA) when you become available again.

    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 the instructor or the TA.

    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) by email to cass@utep.edu. 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)

    August 24: topics to cover:

    August 26: topics to cover:

    August 31: topics to cover:

    see lecture.

    September 2: topics to cover:

    September 7: topics to cover:

    September 9: topics to cover:

    September 14: topics to cover:

    September 16: topics to cover:

    September 21: overview for Test 1.

    September 23: Test 1.

    September 28: overview of Test 1 results.

    September 30: topics to cover:

    October 5: topics to cover:

    October 7: topic to cover:

    October 12: topic to cover:

    October 14: topics to cover:

    see lecture.

    October 19: preview for Test 2

    October 21: Test 2

    October 26: review of Test 2 results

    October 28: topics to cover:

    see lecture .

    November 2: topics to cover:

    November 4: topics to cover:

    see Section 2.1.1 of a paper and comments

    November 9: topics to cover:

    see lecture and Sections 2.2 and 2.3 of the paper.

    November 11: topics to cover:

    see lecture.

    November 16: topics to cover:

    see lecture.

    November 18: topics to cover:

    November 18: preview for Test 3

    November 23: Test 3.

    November 30: topics to cover:

    December 2: preview for final exam.