COURSE OUTLINE CS211 - Theory of Automata and Formal Languages

BS Computer Science (2nd year) Punjab University Course Outline: To see the course outline of all subjects click here. 

CS211 - Theory of Automata and Formal Languages (Paper IX — 100 Marks)

Objectives

The course aims to develop an appreciation of the theoretical foundations of computer science through study of mathematical & abstract models of computers and the theory of formal languages. Theory of formal languages and use of various abstract machines as ‘recognizers’ and parsing will be studied for identifying/validating the synthetic characteristics of programming languages. Some of the abstract machines shall also study as ‘Transducers’. The following topics will be covered in the course: Formal language, Defining Language, Regular Expression, Finite Automata, Transition Graphs, Kleene’s Theorem, Finite Automata with output, Regular Languages, Non regular Languages, Decidability, Demonstration Of JFLAP, Context Free Grammars, Grammatical Formats. Pushdown Automate (PDA), CFG=PDA, Non-Context-Free Languages, Context-Free Languages, Decidability, Turing Machine, The Chomsky Hierarchy.

Prerequisites
Discrete Structures

Text Book
Denial Cohen, Introduction to Computer Theory, John Wiley & Sons, lnc. ISBN-10:0471137723

Reference Material 

• J Hopcraft, D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wisely, 2nd Edition, ISBN-10: 0201441241
• Thomas A. Sudkamp, Languages and Machines, An Intro to the Theory of Comp. Sc., 2/e Addison Wesley. ISBN-I0: 0201821362