Pre-requisite(s)

None

Recommended Book(s)

Introduction To Computer Theory, 2nd Edition, Daniel I. A. Cohen, John Wiley & Sons, Inc., 1997, ISBN 0-471-13772-3.

COURSE OBJECTIVES

After studying this course the students should be able to: Designing models for Software for designing and checking the behavior of digital circuits Lexical Analyzer of a compiler Software for scanning large bodies of text Software for verifying communication protocols

COURSE LEARNING OUTCOMES (CLO)

Course Objectives

COURSE CONTENTS

Introduction

Why this course?
History of computation
Alphabet Sets
Languages in the abstract
Defining a Language
Finite and Infinite Languages
Kleene Closure

Regular Expressions

Method to define a language
Formal definition of Regular Expression
Languages associated with Regular Expressions
Ffinite languages are regular
RE for Even-Even

Finite Automata

Another method to define language
States, transitions, input symbols
FAs and their Languages
Transition Tables of language
FA of even-even

Transition Graph

Relaxing the restrictions on inputs
Generalized transition graphs
Non determinism
Constructing regular expression from TGs
Kleene’s theorem.

Regular and Nonregular languages

Closure properties
complements and intersections
pumping lemma

Finite Automata with Output

Moore Machines
Mealy Machines
Transducers
Practical Applications of Finite Automata

Context-Free grammars

Syntax as a method for defining a language
symbolism for generative grammars
Parse Trees
Ambiguity
Total Language Trees
Leftmost and rightmost derivations
Chomsky’s Normal Form

Pushdown Automata

A new format of FAs
Adding a Pushdown Stack
Deterministic and Non-deterministic PDA
Converting a PDA to CFG and vice versa.

Non-Context-Free and Context-Free Languages

Pumping Lemma for CFLs
Closure Properties of CFLs
Intersection and Complement
Decidability of CFLs.

Turing Machines

The Turing Machine
Variations of Turing Machines
Recursive and Recursively Enumerable Languages
Chomsky’s Hierarchy

MAPPING OF CLOs TO ASSESSMENT MODULES

Final Exam
Assignments
Surprise Tests/Quizzes
Midterm Exam