Theory of Automata and Formal Languages Course Outline - University of Sargodha

Course Title: Theory of Automata and Formal Languages

Course Code: CS-3131

Course Structure: Lectures: 3/ Labs: 0

Credit Hours: 3

Prerequisites: CMP-2111 (Discrete Structures)

Course Objectives:

The course introduces students with fundamental concepts of automata theory and formal
languages to form basic models of computation which provide foundation of many branches of
computer science, e.g. compilers, software engineering, concurrent systems, etc.

Course Syllabus:

Introduction to Automata.Finite Automata.Regular Expressions and Languages.Properties of

Regular Languages.Context-Free Grammars and Languages.Pushdown Automata.Properties of

Context-Free Languages.Turing Machines.Un-decidability.Intractable Problems.

Course Outline:

1.      Introduction to Automata: The Methods and the Madness, Introduction to Formal Proof,
Inductive Proofs, The Central Concepts of Automata Theory. [TB: Ch.1]

2.      Finite Automata: Introduction of Finite Automata, Deterministic Finite Automata,
Nondeterministic Finite Automata, Finite Automata With Epsilon Transitions. [TB: Ch.2]

3.      Regular Expressions and Languages, Regular Expressions, Finite Automata and Regular
Expressions, Applications of Regular Expressions, Algebraic Laws for Regular
Expressions. [TB: Ch.3]

4.      Properties of Regular Languages, Proving Languages Not to Be Regular, Closure
Properties of Regular Languages, Decision Properties of Regular Languages,
Equivalence and Minimization of Automata. [TB: Ch.4]

5.      Context-Free Grammars and Languages: Context-Free Grammars, Parse Trees,
Applications of Context-Free Grammars, Ambiguity in Grammars and Languages

6.      Pushdown Automata: Definition of the Pushdown Automaton, The Languages of a PDA,
Equivalence of PDAs and CFGs, Deterministic Pushdown Automata. [TB: Ch.6]

7.      Properties of Context-Free Languages: Normal Forms for Context-Free Grammars, The
Pumping Lemma for Context-Free Languages, Closure Properties of Context-Free
Languages, Decision Properties of CFLs. [TB: Ch.7]

8.      Introduction to Turing Machines: Problems That Computers Cannot Solve, The Turing
Machine, Programming Techniques for Turing Machines, Extensions to the Basic Turing
Machine, Restricted Turing Machines, Turing Machines and Computers. [TB: Ch.8]

9.      Un-decidability: A Language That Is Not Recursively Enumerable, Un-decidable
Problem That Is RE, Un-decidable Problems About Turing Machines, Posts
Correspondence Problem, Other Un-decidable Problems. [TB: Ch.9]

10.  Intractable Problems: The Classes P and NP, An NP-Complete Problem, A Restricted
Satisfiability Problem. [TB: Ch.10]

Textbook(s):

•         Introduction to Automata Theory, Languages, and Computation by J. Hopcroft, R.
Motwani, and J. Ullman, 3^rdEdition, 2006, Addison-Wesley.

Reference Material:

•         An Introduction to Formal Language and Automata by Peter Linz, Jones & Bartlett Pub;
4^thEdition (2006). ISBN-10: 0763737984

•         Automata and Formal Languages: An Introduction by Dean Kelley, Prentice Hall (1995).
ISBN-10: 0134977777

Note: This content is obtained from official documents of University of Sargodha and applied on BS Computer Science for Main Campus, Sub Campuses, and Affiliated Colleges.