CS 3350: Automata, Computability, and Formal Languages

Fall 2019

  • Instructor: Vladik Kreinovich, email vladik@utep.edu, office CCSB 3.0404,
    office phone (915) 747-6951
  • Class time: Mondays and Wednesdays 12-1:20 pm, CCSB 1.0202.
  • Details: Syllabus

Faculty office hours

  • The instructor's office hours are Mondays and Wednesdays 1:30-3 pm, 4:30-5: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: 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.

Instructional Assistant (IA):

    Carlo Alvarado, email caalvarado7@miners.utep.edu, office hours Tuesdays and Thursdays 10 am - 12 pm in Room CCSB G.0512 or by appointment.

Instructor of another section of Automata:

    Daniel Mejia, email dmmejia2@miners.utep.edu, office hours Mondays and Wednesdays 1:30-3 pm in CCSB 3.1018, or by appointment.

Instructional Assistant (IA) for another section of Automata:

    Alain Sanchez, email asanchez74@miners.utep.edu, office hours Tusday through Thursday 10 am - 12 noon and Friday 8-10 am in Room CCSB G.0512 or by appointment.

Home assignments


  • Spring 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
  • Clarifications on Church-Turing thesis

Department of Computer Science | The University of Texas at El Paso