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)

Notes

• การบ้านครั้งที่ 3 (pdf) (ต้องดูภาพในหนังสือหน้า 84 ประกอบ)
• คะแนนสอบกลางภาค: (xls)
• การบ้านโปรแกรมครั้งที่ 1: (rar)
• การบ้านครั้งที่ 2: ในหนังสือเรียน ข้อ 1.8.5, 2.1.3, 2.2.1 และ 2.2.3 กำหนดส่งวันที่ 17นี้ (pdf)
• การบ้านครั้งที่ 1 (pdf)
• ใบแก้คำผิดหนังสือ Elements of the Theory of Computation (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%