نیمسال دوم 1386-1385

نظريه زبانها و ماشينها

Finite Automata

مدرس

دکتر محمد حسن شیرعلی شهرضا

E-mails: hshirali AT yazduni.ac.ir   shahreza AT shirali.ir
Website: http://shahreza.shirali.ir

کتاب درس

مقدمه‌ای بر نظريه محاسبات ، نویسنده: مايكل سيپسر،
مترجم : دكتر محمدحسن شيرعلی شهرضا، انتشارات دانشگاه یزد، 1385

Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 1997, ISBN: 0 – 534 – 94728

کتابهای کمک درس

E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to automata theory, languages, and computation, 2nd edition, Addison-Wesley, 2001
Peter Linz, An Introduction to Formal Languages and Automata, 3rd edition, Jones and Bartletts, 2000. ISBN 0-7637-1422-4

سرفصل

Chapter 0 Introduction
Chapter 1 Regular Languages
Chapter 2 Context-Free Languages
Chapter 3 The Church-Turing Thesis
Chapter 4 Decidability
Chapter 5 Reducibility
Chapter 6 Advanced Topics in Computability Theory
Chapter 7 Time Complexity
Chapter 8 Space Complexity
Chapter 9 Intractability
Chapter 10 Advanced Topics in Complexity Theory

نحوه محاسبه نمره درس: (Grading)

1 - امتحان ميان ترم بصورت تستي برگزار خواهد شد
2 - هر دانشجوي اين درس چهار سري تمرين تحويل مي‏دهد. (هر سری 0.5 نمره، جمعا 2 نمره)
3 - امتحان پايان ترم بصورت تشريحي برگزار خواهد شد