Webpage of

Umar Faiz

Last updated

Dec 31, 2008

Academics

Program Name:

Bachelor in Computer and Information Sciences

Instructor:

Umar Faiz
Dept. of Computer and Information Sciences
Office: B-206
email: umarfaiz (at) pieas edu pk

Course Code/Credit hrs:

(CIS 317) Theory of Automata (3 Credit hrs)
1 Contact Hour is equivalent to 60 minutes. 1 Lab credit is equivalent to 3 contact hours.

Class Coordinates:

Room No# B-106
Monday, Tuesday & Friday

Learning outcomes:

On the completion of this course, the student should be able to:

• Understand the theory of computation through formal languages and abstract computing devices (automata)
• Apply a number of proof techniques to theorems in language design
• Understand the equivalence between Nondeterministic Finite State Automata and Deterministic Finite State Automata.
• Understand the equivalence between Context-Free Grammars and Nondeterministic Pushdown Automata.
• Appreciate the power of the Turing Machine, as an abstract automaton
• Relate the results of computation theory to real-world computational problems

Course Description:

The course explores the language theory and computability. Language theory includes: regular expressions, regular languages, finite automata (deterministic and non-deterministic), context-free languages, pushdown automata, and language grammars. Computability includes: Turing machines and their computing power, unsolvable problems, and intractable problems (NP-Completeness).

Course Objectives:

• To study the construction of different proof techniques.
• To study e the language representation by a regular
• To construct deterministic finite automaton accepting a given language
• To draw a state diagram for a finite automaton (deterministic or nondeterministic)
• To find a minimum-state equivalent deterministic finite automaton
• To use a grammar to generate or accept a string and to study the derivation of a string and draw the corresponding parse tree(s)
• To construct a context-free grammar for a language
• To construct a pushdown automaton that accepts a given language
• To study the closure properties of the regular languages and context-free languages.
• To study different types of Turing machines and create a Turing machine to solve a specified problem
• To determine whether a problem about Turing machines is solvable or undecidable
• To arrange classes of languages in order of increasing generality and to discuss relative computational power of language recognizers

Pre-requisites

Discrete Mathematics

Textbooks/ Course URL

Course Text:

• J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Language, and Computation. Addison–Wesley, 2nd Edition, 2001.

Recommended Books:

1. Peter Linz, An Introductionto Formal Languages and Automata. Jones and Bartlett, 4th Edition, 2006.
2. Michael Sipser, Introduction to the Theory of Computation. Thompson Course Technology, 2nd Edition 2006.
3. Meduna, A. 2000, Automata and Languages : Theory and Applications, Springer Verlag
4. Bakhadyr Khousinov, Ail Nerode, Automata Theory and Its Application, Birkhauser Boston, 2001

Course URL:

http://www.pieas.edu.pk/umarfaiz

Assignments:

Assignments represent your opportunity to learn the material and you are not responsible for mastery of the material until the midterm and final exams. Thus, assignment solutions themselves are not graded. Hands-on practice is necessary to achieve the required level of understanding and technical ability. Exercises are assigned that help achieve these objectives. It is strongly advised to attempt all assigned exercises to familiarize yourselves with the concepts and techniques.

Lectures, Tutorials & Attendance Policy:

Teaching Method(s):
Lectures, Tutorials
Teaching Media: Slides, handouts
There will be 48 sessions of 60 minutes each. 80% attendance is mandatory

Grading/Grading Policy:

Quizzes/Assignments [20%]
Sessional I/Sessional II [30%]
Final Exam [50%]

(Grades will be given as per PIEAS’ Policy (see prospectus for further details)
There will be absolutely no makeup quizzes. Makeup midterm will only be allowed in case of extreme emergency. Contact the instructor as soon as the emergency permits to discuss possible course of action depending on the extremity of the emergency. For credit all assignments must be turned in time. Late assignments will not earn any credit but to get a passing grade all assignments must be eventually turned in.

Rules and Regulations:

In addendum to Institute’s policy following rules will be strictly adhered to:
Attendance: Students are expected to attend course sessions. In case of any absence, students are responsible to make up for the course covered in the missed session. Attendance profile is consistently compiled and updated at the department and it is mandatory to meet the minimum requirements of 80% to qualify for appearance in the final examination.
Class Behaviour: Cell phones must be turned off when the student enters the classroom. Disruption of class by a cell phone may lead to expulsion from the class.
Academic Honesty: Academic integrity is the foundation of the academic community. Each student has the primary responsibility for being academically honest, students are advised to read and understand all sections of this policy relating to standards of conduct and academic life.
Plagiarism: Plagiarism involves the use of quotations without quotation marks, the use of quotations without indication of the source, the use of another's idea without acknowledging the source, the submission of a paper, laboratory report, project, or class assignment (any portion of such) prepared by another person, or incorrect paraphrasing.

Topics Coverage:

• Overview and introduction (Lectures 1-3)
• Deterministic finite automata (Lectures 4-6)
• Nondeterministic finite automata (Lectures 6-9)
• Equivalence of DFAs and NFAs (Lectures 10-11)
• Regular expressions and languages, Properties of regular languages, Applications of Regular expressions, Algebraic Laws for Regular expressions (Lectures 12-15)
• Closure properties of regular languages, Decision Properties of Regular Languages, Equivalence and Minimization of Automata, Pumping Lemma for Regular languages (Lectures 16-18)
• Context-free grammars , Left Linear and Right Linear grammars, Parse Trees, Ambiguity (Lectures 19-21)
• Pushdown automata , Acceptance by empty stack, Acceptance by final state , (Lectures 22-23)
• Equivalence of the two Methods of PDA Acceptance, Equivalence of PDAs and CFGs (Lectures 24-27)
• Simplification of context-free grammars, normal forms, Closure properties of CFLS, Decidable properties of CFLs, Pumping Lemma for CFL’s (Lectures 28-32)
• Turing Machines, Recursive and Recursively Enumerable, Turing Machines construction, Different Models of TM, Equivalence of TMs (Lectures 33-39)
• TMs as enumerators, Recursive and Recursively Enumerable Sets Enumerators, Closure properties of Recursive and Recursively Enumerable languages, Decidability, Halting Problem, (Lectures 40-48)

Weekly Course Plan: