CS402 - Theory of Automata
Course Page
Q & A
Course Category: Computer Science/Information Technology
Course Level: Imdregraduate
Credit Hours: 3
Pre-requisites: N/A

Course Synopsis

This is an introductory course on Theory of Automata. Students are introduced to the concept of Formal Language and Automata. Formal Languages cover recursive definitions of languages, regular grammar, regular expression, context free grammar and language. In Automata they learn about finite automata (deterministic; non-deterministic),transition graphs and pushdown automata (deterministic; non-deterministic). They also learn about fundamental concept of Moore and Mealy machines and Turing machines.

Course Learning Outcomes

At the end of the course, you should be able to:
  • Explain different methods for defining languages
  • Discuss what Finite Automata is
  • Differentiate between Regular Languages and NonRegular Languages
  • Describe Context-free languages and context-free grammars, parse trees, derivations and ambiguity; Basic concepts of pushdown automata
  • Explain basic definitions and relation to the notion of an algorithm or program

Course Contents

Languages, Kleen Closure, Recursive Definitions, Regular Expressions, Finite and Infinite languages, Regular Languages, NonRegular Languages, Finite Automata with output, Finite Automata and their languages, Transition Graphs, Nondeterminism, NonRegular Languages, The Pumping Lemma, Context Free Grammars, Tree, Ambiguity, Pushdown Automata, Decidability

Course Related Links

Basic Tutorials relating to Theory of Automata
Definitions of important concepts relating to Theory of Automata
Introduction to the subject of Theory of Automata
Definitions of Regular Language and Regular Expression
Dictionary of Computer Science related terms

Course Instructor

Dr. Shahid Siddiqi
Ph.D. (Computational Mathematics) Brunel University (University of West London), England.

Introduction to Computer Theory by Daniel I. A. Cohen

Introduction to Languages and the Theory of Computation by John C. Martin