نظرية الحوسبة أحد فروع المعلوماتية النظرية theoretical computer science التي تدرس مسائل قابلة للحل حاسوبيا solvable computationally باستخدام نماذج مختلفة للتحسيب تكمن اهمية هذه المادة في انها مدخل مهم لفهم معالجة اللغة الطبيعية Natural language processing في مجال اللغويات الحاسوبية Computational Linguistics
Course Description:
This course will provide a foundation and principles to the “Theory of Computation”. The students will realize that the sometimes chaotic technology تكنولوجيا الفوضى oriented world of computers has a very elegant mathematical basis to it. This basis is deeply rooted in mathematics developed before the days of modern computers. Our study will lead to some interesting implications concerning the theoretical limits of computing. On the practical side, this course is a background for a course on compilers بناء المترجمات . Topics covered in this course include: mathematical prerequisites, finite state machines (automata), concept of a language and grammars, deterministic and non-deterministic accepters, regular expressions and languages, context-free languages, pushdown automata, Turing machines,
The course covers four broad areas: (1) Finite automata and regular expressions, (2) Context-free grammars, (3) Turing machines and decidability, and (4) the theory of intractability, or NP-complete problems.
1: Finite Automata
2: Regular Expressions and Properties of Regular Languages
3: Context-Free Grammars and Languages
4: Properties of Context-Free Languages, plus introduction to Turing Machines
5: Turing Machines and Undecidability
6: Intractable Problems (NP-Completeness)
Text Book:
Peter Linz, "An Introduction to Formal Languages and Automata",5th ed., Jones and Bartlett, 2011 , you can download the pdf file for this book below