Theoretical Computer Science : TYBCS : SPPU : Syllabus

 Course Contents

Chapter 1 Finite Automaton 

Introduction: Symbol, Alphabet, String, Prefix & Suffix of Strings, Formal

Language, Operations on Languages.

Deterministic finite Automaton – Definition, DFA as language recognizer,

DFA as pattern recognizer.

Nondeterministic finite automaton – Definition and Examples.

NFA To DFA (Myhill Nerode Method)

NFA with ε- transitions Definition and Examples.

NFA with ε-Transitions to DFA & Examples

Finite automaton with output – Mealy and Moore machine, Definition and

Examples.

Minimization of DFA, Algorithm & Problem using Table Method

Chapter 2 Regular Expressions and Languages 

Regular Expressions (RE): Definition & Example

Regular Expressions Identities.

Regular language-Definition and Examples.

Conversion of RE to FA-Examples.

Pumping lemma for regular languages and applications.

Closure Properties of regular Languages

.Chapter 3 Context-Free Grammars and Languages 

Grammar - Definition and Examples.

Derivation-Reduction - Definition and Examples.

Chomsky Hierarchy.

CFG: Definition & Examples. LMD, RMD, Parse Tree

Ambiguous Grammar: Concept & Examples.

Simplification of CFG: Removing Useless Symbols, Unit Production, ϵ-production and

Nullable Symbol.

Normal Forms: Greibach Normal Form (GNF) and Chomsky Normal Form (CNF)

Regular Grammar: Definition.

Left linear and Right Linear Grammar-Definition and Example.

Equivalence of FA & Regular Grammar

Construction of regular grammar equivalent to a given DFA.

Construction of a FA from the given right linear grammar

Chapter 4 Push Down Automata 

Definition of PDA and examples.

Construction of PDA using empty stack and final State method: Examples using stack

method.

Definition DPDA & NPDA, their correlation and Examples of NPDA

CFG (in GNF) to PDA: Method and examples

Chapter 5 Turing Machine

The Turing Machine Model, Definition and Design of TM

Problems on language recognizers.

Language accepted by TM.

Types of Turing Machines (Multitrack TM, Two-way TM, Multitape TM, Nondeterministic TM)

Introduction to LBA (Basic Model) & CSG. (Without Problems)