The course aims to provide the students with a general knowledge on a variety of issues in the mathematical development of computer science theory, particularly finite representations for languages and machines, as well as gain a more formal understanding of algorithms and procedures. Applications to compilers, string searching, and control circuit design are discussed. The hierarchy of finite state machines, pushdown machines, context free grammars and Turing machines are analyzed, along with their variations. The notions of decidability, complexity theory and a complete discussion of NP-Complete problems round out the course.

Learning Outcomes

CTPO

TOA

Upon successful completion of the course, the students will be able to :

LO - 1 :

Construct RE, FA, PDA, CFG, TM and PM for defined languages.

1,8

1,

LO - 2 :

Prove the equivalence of languages described by FA and RE, the equivalence of languages described by PDA and CFG, the equivalence of languages described by TM and PM.

1,8

1

LO - 3 :

Make connection between theoretic machines and current computers.

1,8

1

LO - 4 :

Apply mathematical models to solve problems in diverse areas such as string searching, cryptography, and language design.

1,8

1

CTPO : Contribution to programme outcomes, TOA :Type of assessment (1: written exam, 2: Oral exam, 3: Homework assignment, 4: Laboratory exercise/exam, 5: Seminar / presentation, 6: Term paper), LO : Learning Outcome

Contents of the Course

AUTOMATA THEORY : Languages, Recursive Definitions, Regular Expressions, Finite Automata, Transition Graphs, Kleene's Theorem, Finite Automata with Output, Regular Languages, Nonregular Languages (The Pumping Lemma, Myhill-Nerode Theorem), Decidability. PUSHDOWN AUTOMATA THEORY : Context-Free Grammars (Trees, Ambiguity), Grammatical Format (Regular Grammars, Chomsky Normal Form, Leftmost Derivations), Pushdown Automata, CFG=PDA, Non-Context-Free Languages (The Pumping Lemma for CFLs), Context-Free Languages (Closure Properties), CYK Algorithm. TURING THEORY : Turing Machines (TM), Post Machines, Minsky's Theorem, Variations on the TM (The Move-in-State Machine, The Stay-Option Machine, The k-Track TM, The Two-Way Infinite TAPE Model, The Nondeterministic TM, The Read-Only TM) , TM Languages (The Encoding of Turing Machines, The Universal Turing Machines, Halting Problem), The Chomsky Hierarchy (Phrace-Structure Grammars, Context-Sensitive Grammars), Computers (Computable Functions, Church's Thesis).

Course Syllabus

Week

Subject

Related Notes / Files

Week 1

Languages

Week 2

Recursive Definitions

Week 3

Regular Expressions

Week 4

Finite Automata

Week 5

Transition Graphs

Week 6

Kleene's Theorem

Week 7

Finite Automata with Output

Week 8

Regular and Nonregular Languages

Week 9

Mid-term exam

Week 10

Context-Free Grammars

Week 11

Push-Down Automata

Week 12

Turing Machines

Week 13

Post Machines

Week 14

Minsky's Theorem

Week 15

Variations on the TM

Week 16

End-of-term exam

Textbook / Material

1

Yarımağan, Ünal. 2011, Özdevinirler (Otomatlar) Kuramı ve Biçimsel Diller

2

Cohen, D. 1997; Introduction to Computer Theory (2nd).

3

Sipser, M. 2013; Introduction to Theory of Computation (3rd).