204213 Theory of Computation src:52

Instructor : วัชรพัฐ เมตตานันท

Section : 800, 801

Class : 800: Th 9.00-12.00, 801: Th 13.00-16.00

Room: 5201

Office hour : Tu 13.00-15.00, W 10.00-13.00

Syllabus : (pdf)

Course Overview

• Introduction Sets, Relations, Functions
• Strings and Languages, Regular expressions
• DFA and NFA
• Regular Languages
• State minimizations
• Languages that are not regular
• Context-free languages
• RL is a subset of CFL
• PDA
• CFG=PDA
• Languages that are not context-free
• Turing Machine
• Universal TM and Grammar
• Undecidability
• Conclusions

Books

Harry R. Lewis, Christos H. Papadimitriou. Elements of the Theory of Computation. 2nd Edition

Grading

• Mid: 35%
• Final: 40%
• H.W. 15% = Paper sheets 10% + Programs 5%
• Quizes: 10%