CS 476: Automata Theory and Formal Languages

Spring 2022


Finite automata, regular expressions, regular languages and their properties, the pumping lemma. Context free grammars and languages, normal forms, pushdown automata, the pumping lemma for the CFLs. Turing machines and their properties. Decidability and undecidable languages. Complexity theory, NP-completeness. Credit units: 3 ECTS Credit units: 6, Prerequisite: CS 201.

Textbook: Introduction to the Theory of Computation,  Cengage Learning, Michael Sipser

Grading: There will be one midterm exam (25%), a final exam (35%). 3 classworks (10% each), and 10 quizzes (1% each).

Quizzes: At least 10 quizzes, every Thursday unless otherwise announced.

Classworks will be announced, we expect to hold 3 classworks total. Classworks will be open notes unless we switch to a full online schedule depending on the course of the pandemic.

Midterm and final exams are closed notes, closed book.

Passing Grade: No predetermined grade to pass the course.

FZ Policy: [(Classworks' Average x 0.3) + (Midterm x 0.25)] should be at least 18 (out of 55).

Makeup Policy: Medical report holders will be entitled for the midterm make up, and ONLY ONE classwork makeup in the last week of the semester. Classwork makeup will be comprehensive, and both midterm and classwork makeups will definitely be more difficult. We will give no makeups for the quizzes.


  • Planned Lecture Cancellations

  • The following lectures are canceled.

    • Outline (tentative):

    Lecture notes below are downloadable only within Bilkent network. Use VPN to access from home.
    Week Topic Lecture Notes LaTeX Source Notes (tentative)
    1 Introduction & Finite Automata 0-intro.pdf      intro slides
    		 0-intro.tar.gz
    2 Finite Automata 1-dfa.pdf
    dfaMod.c
    		 1-dfa.tar.gz
    3 Finite Automata 2-nfa.pdf
    		 2-nfa.tar.gz
    4 Regular expressions and languages 3-re.pdf
    		 3-re.tar.gz
    5 Context-free grammars and languages


    6 Context-free grammars and languages 4-cfg.pdf 4-cfg.tar.gz
    7 Context-free grammars and languages 5-pda.pdf
    		 5-pda.tar.gz
    		 Classwork 1
    8 Pushdown automata

    		Midterm
    9



    10 Turing machines 6-tm.pdf 6-tm.tar.gz
    11 Decidability, Reducibility


    12 Complexity theory and NP-completeness 7-decidability.pdf
    8-reducibility.pdf     		7-decidability.tar.gz
    8-reducibility.tar.gz     		Classwork 2
    13 Complexity theory and NP-completeness


    14 Complexity theory and NP-completeness Cook-Levin-Theorem.pdf
    9-complexity.pdf

     

    Important information for exams and classworks

    The following is on the cover pages of your midterm and final exams. Most students do not read this *valuable* information, but everyone SHOULD. These rules apply to classworks as well:

    1. Write legibly, and make your answers clear.
    2. Provide comprehensible diagrams for state machines (DFA, NFA, PDA, TM).
    3. Unintelligible answers may fail to receive credit.
    4. All proofs should be presented formally, and should follow the styles presented in class.
    5. Handwaving arguments will be considered incorrect.
    6. Ambiguous explanations and proofs will be considered incorrect.
    7. Use notations the same way as described in class.
    8. Closed book, closed notes, no cheat sheets.
    9. NO phones/tablets/laptops etc. other than those you need to use to join the Zoom session.

    The rules 4 and 5 above point out the fact that this course is a FORMAL, THEORY course. All proofs should be presented as formal expressions, the same way discussed in class. Long paragraphs/sentences of trying to explain a possible answer does not mean that you will receive any credit. This is not a humanities course, do not write essays to answer the questions.

    Let us reiterate
    1. THIS IS A THEORY COURSE. THIS IS A MATHEMATICS COURSE. NOTATIONS ARE EVERYTHING. USE NOTATIONS ONLY AS DESCRIBED IN CLASS, AND ONLY AS DESCRIBED IN CLASS. NOTATIONS YOU HAVE SEEN ELSEWHERE (INCLUDING THE TEXTBOOK) MAY CAUSE DEDUCTIONS IN CREDITS TOTALING UP TO ALL THE POINTS A QUESTION IS WORTH. WE WILL NOT TRY TO UNDERSTAND WHAT YOU ARE PRESENTING WHEN ANSWERING A QUESTION, WILL NOT GUESS WHAT YOUR NOTATIONS MEAN.
    2. THERE IS NO SUCH THING AS "PROOF BY EXAMPLE" EXCEPT "PROOF BY CONTRADICTION".
    3. JUST BECAUSE YOU WROTE "SOMETHING", IT DOESN'T MEAN YOU WILL GET ANY PARTIAL CREDIT IF YOUR ANSWER HAS NOTHING TO DO WITH THE QUESTION.


    Frequently Asked Questions