CS 3350: Automata, Computability, and Formal Languages

Spring 2020

• Instructor: Vladik Kreinovich, email vladik@utep.edu, office CCSB 3.0404,
  office phone (915) 747-6951
• Class time: Tuesdays and Thursdays 9-10:20 am, LART 206.
• Details: Syllabus

Faculty office hours

• The instructor's office hours are:
  • Tuesdays 8:30-9 am and 10:30-12:30 pm,
  • Thursdays 8:30-9 am, 10:30-12 pm, 1-1:30 pm,
  • or by appointment.
• If you want to come during the scheduled office hours, there is no need to schedule an appointment.
• If you cannot come during the instructor's scheduled office hours, please schedule an appointment in the following way:
  • use the instructor's appointments page http://www.cs.utep.edu/vladik/appointments.html to find the time when the instructor is not busy (i.e., when he has no other appointments), and
  • send him an email, to vladik@utep.edu, indicating the day and time that you would like to meet.
  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):

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.

Home assignments

Homeworks

Resources

• Fall 2019 CS 3350 class Web page
• How to transform a context-free grammar into a (non-deterministic) pushdown automaton, pdf file
• V. Kreinovich and O. Kosheleva, "A Turing Machine Is Just a Finite Automaton with Two Stacks: A Comment on Teaching Theory of Computation", pdf file
• V. Kreinovich, A. Lakeyev, J. Rohn, and P. Kahl, "The notions of feasibility and NP-hardness: brief introduction", Chapter 2 from "Computational complexity and feasibility of data processing and interval computations", Kluwer, Dordrecht, 1997. pdf file
• B. W. Robertson, V. Kreinovich, and O. Kosheleva, "How to Make a Proof of Halting Problem More Convincing: A Pedagogical Remark", International Mathematical Forum, 2018, Vol. 13, No. 1, pp. 9-13. pdf file

Tests

• Test 1
• Solutions to Test 1
• Test 1: typical mistakes
• Test 2
• Solutions to Test 2
• Test 3
• Solutions to Test 3
• Final Exam

Quizzes

Logistics of April-May classes:

Logistics

Materials for April-May classes:

• April 2: Turing Machines. 1
• April 7: How to Simulate a Turing Machine?; see also handout
• April 9: Section 2.1.1 of a handout
• April 14: P, NP, etc.: Brief Summary and Sections 2.2 and 2.3 of the handout
• April 16: Proof by Contradiction: A Classical Example
• April 21: Halting Problem
• April 23: Church-Turing Thesis
• May 7: Decidable and Semi-Decidable Languages