CMPS 642 - Automata Theory and Formal Languages

Automata Theory and Formal Languages - CMPS 642

Class Meeting: Friday 08:00 - 10:00

Course Objectives:

The course aims to provide students with a review of the fundamentals of theory of computation, variants of Turing Machines, nondeterministic Turing Machines, enumerators, decidability, the halting problem, the diagonalization method, Turing unrecognizable languages, and reducibility.

Course Outcomes:
  
    1. Student will be able to understand the different formal languages and different abstract machines recognizing them.
    
    2. Student will be able to learn how to design a deterministic and non deterministic finite state machine.

    3. Student will be able to distinguish between regular language and non regular language and use the pumping lemma to prove that a language is non regular.
    
    4. Student will be able to learn how to design a context free grammar and push down automata in order to recognize a certain context free language.

    5. Student will be able to distinguish between context free languages and non context free languages and use the pumping lemma to prove that a language is non context free.

    6. Student will be able to understand turing machines and how they work.

    7. Student will be able to understand decidable and undecidable language and use the mathematically proving to prove the undecidability of a language.

    8. Students will gain knowledge about the complexity theory.

Download course syllabus as PDF