King Fahd University of Petroleum & Minerals

Information & Computer Science Department

ICS 354 - Automata and Language Translation Systems

Term 061

Instructor:

Dr. Sultan Almuhammadi

Office: Building 22 - Room 320

Phone: 860-1625

Email: sultanm@ccse.kfupm.edu.sa

Course Textbook:

P. Linz, An Introduction to Formal Languages and Automata, Jones and Bartlett, 2001.

Grading Policy:

Homework and Class Activities 20%

(Including: attendance, assignments,

participation, discussion, quizzes)

Major Exam I 25%

Major Exam II 25%

Final Exam 30%

Note:

Check the class website / webCT regularly for new updates.

Course Contents (tentative):

1. Introduction to alphabet, languages, and regular expressions.

2. Regular Languages. Finite-state automata, DFA and NFA. Equivalence of DFA and NFA.

3. Overview of Theory of Computation: solvable and unsolvable problems.

4. Pigeon-hole principle, pumping lemma, and non-regular languages.

5. Grammar, Context-Free and Context-Sensitive Grammar.

6. Context-Free Languages and Pushdown Automata.

7. Turing Machines. Recursive and Recursively enumerable languages. Linear bounded automata.

8. Hierarchy of Formal Languages and the Chomsky Hierarchy.

9. Undecidability, the Halting Problem, Hilbert 10th Problem. Reducibility and Rice’s Theorem.

10. Informal overview of Gödel Incompleteness Theorem.

11. Introduction to Computational Complexity: classical time and space classes in the context of Turing Machines.

Notes and guidelines:

1. Class activities include: participation, online and in-class discussions, attendance and quizzes.

2. Regular attendance will be maintained during this course. Exceeding nine absences will result in a DN grade.

3. If you find out that you may miss a class for some reason, you have to email the instructor ahead of time (12 hours before the class). This helps the instructor estimating the number of students for a better planning of the class time.

4. No makeup homework, quizzes or exams would be given.

5. Solutions of homework assignments must be submitted by the deadline, which is the start of the lecture on that deadline day. The deadlines will be firm. Late submission is subjected to a 50% penalty if it is submitted within a week from the deadline and before the coming exam. All homework solutions must have a header on the first page (showing course number ICS 354, student’s name, his ID, and HW #. The format is given on the assignment page)

6. Assignments should be done individually. Discussing problems prior to working them out is highly encouraged as long as writing them down is done individually.

7. Cheating in quizzes or exams in any form will result in disciplinary action as per university rules.