HOME

Course Outline

Course Description

Grading Policy

Syllabus Content

 

     AUTOMATA AND COMPLEXITY THEORY (CS 311)

Course Outline

Instructor: Humaira Kamal Year: 2001-2002
Office: Room 230 Quarter: Summer
Email: humairak@lums.edu.pk Category: Junior
Extension: 2230  
Office Hours: TBA  
TA for the Course: Saad A. Hussain  

Course: CS 311: Automata and Complexity Theory (4 units)

Description:
    This is an introductory course on the theory of computation. Students are introduced to the concept of formal languages and automata. Formal languages cover regular grammar, regular expression, context free grammar and language. In automata they shall learn about finite automata (deterministic and non-deterministic) and pushdown automata. They shall also learn about fundamental concepts of Turing machines.

Core/Elective: Elective

Pre-requisites: Discrete Mathematics (CS 211)

Text:

1) Peter Linz, ‘An Introduction to Formal Languages and Automata', 1990.
2) Some handouts may be given to supplement the text.

Reference:

Daniel I. A. Cohen, ‘Introduction to Computer Theory', 2nd Edition, 1997, John Wiley & Sons, Inc. 

Lectures: There shall be 25 sessions of 80 minutes each

Grading:

  • 30% Quizzes / Assignments
  • 35% Midterm Exam
  • 35% Final Exam

 

Topics

Sessions

Readings

Introduction to the Theory of Computation

1

Chapter 1
Finite Automata (Deterministic Finite Accepters, Non-deterministic Finite Accepters, Equivalence of DFA and NFA etc.)

4

Chapter 2
Regular Languages and Regular Grammars (Regular Expressions, Connection between Regular Expressions & Regular Languages, Regular Grammars etc.)

3

Chapter 3
Properties of Regular Languages

2

Chapter 4
Context Free Languages (Context Free Grammars, Left and Right Most Derivations, Derivation Trees and Sentential Forms)

3

Chapter 5
MIDTERM

1

 
Simplification of Context Free Grammars and Normal Forms

2.5

Chapter 6
Pushdown Automata (Non-deterministic Pushdown Automata, Pushdown Automata and Context Free Languages, Deterministic Pushdown Automata.)

3.5

Chapter 7
Turing Machines (Turing Machines as Language Accepters, Turing Machines as Language Transducers, etc.)

3.5

Chapter 9
Recursive and Recursively Enumerable Languages

1.5

Chapter 11
FINAL EXAM    

 BACK TO TOP

 Last Updated:
30/05/2002

Contact the instructor at: humairak@lums.edu.pk
Contact the TA at:
02020128@lums.edu.pk