CSC 551 Syllabus (Fall Semester 2007)

Automata, Formal Languages and Computability (graduate level)

Credit hours: 3

Goals of the course: The goal of this course is to study fundamental aspects of computation. We will examine different formal models of computers, trying to understand precisely what can and what cannot be computed using given programming constructs. The theory of automata and formal languages has applications in various fields of computer science, including programming languages, compilers, natural language processing, and digital hardware design.

Recommended textbooks: I will not follow a single textbook in this course, listed below are some textbooks which I recommend:

• M. Sipser, Introduction to the Theory of Computation, 2/e, 2005.
• J. Martin, Introduction to Languages and the Theory of Computation, 2002.
• H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, 2/e, 1997.

##### Topics (tentative):

Preliminaries (sets, relations, graphs, trees, proof techniques). Regular Languages (finite automata, regular expression, closure properties, pumping lemma). Context-Free (CF) Languages (CF grammars, push-down automata, closure properties, pumping lemma). Turing Machines and Computability (recursive and recursively enumerable languages, universal machines, undecidable languages, Church-Turing thesis, Rice's theorem, Post Correspondence Problem). Complexity.

Evaluation:

Assignments: 25 points; Quiz: 10 points; Midterm exam: 20 points; Final exam: 45 points

Yahoo group for this course: You must subscribe to the group in order to post/download materials. To join, send a short email to: CSC551-M-KSU-subscribe@yahoogroups.com

To experiment with formal languages topics including determinstic finite automata, nondeterministic finite automata, nondeterministic pushdown automata and Turing machine try JFLAP.

Feel free to download from the stuff below!

### CSC551_Materials

 Modified By

Conversion NFA to DFAعقيل محمد مصطفى عبدالرحمن العظ
Conversion PDA to CFGعقيل محمد مصطفى عبدالرحمن العظ