CMS-A-CC-6-14-TH: Theory of Computation. Core Course-14: Theory, Credit:04, Contact hours: 60.

 Finite Automata

Definition of a Finite Automaton, Model, Representation, Classification – with respect to

output function Mealy and Moore Machines, with respect to State Transition –

Deterministic and Non-Deterministic Machine, Examples, conversion algorithms Mealy

to Moore and Moore to Mealy, Finite and Infinite state machines, Finite Automaton,

Deterministic and Non-Deterministic Finite automaton, Non-Deterministic to equivalent

Deterministic Automaton-Optimized and Non-optimized technique ideas and algorithms,

Acceptability of String by a Finite Automaton.

15 hours

Formal Languages and Grammar

Introduction to Formal Grammar and Language, Chomsky’s Classification of Grammar –

Type-0, Type-1 or Context Sensitive, Type-2 or Context Free and Type-3 or Regular

Grammar, Illustration of each of these classes with example, Sentential form, Sentences –

Languages or strings, Derivations, Ambiguous Grammar and Language, Designing of

Grammar for a language, Find the Language for given Grammar, Definition and basic

idea about Push Down Automaton.

15 hours

Regular Expression:

Basic Idea and Definition, Regular Expression basic Identities, Arden’s Theorem –

Statement (without Proof) and application for reduction of equivalent regular expressions,

Regular expression to Finite Automata conversion, State Transition System to Regular

Expression conversion algorithm by Arden’s Algebraic Method, FA to Regular Grammar

and Regular Grammar to FA conversion algorithms and applications.

15 hours

Turing Machine

Concepts of Turing Machine, Formal Definitions, Classifications – Deterministic and

Non-Deterministic Turing Machines, Simple Design of Turing Machines: Odd / even

count and concepts of Universal Turing Machines, Difference and Similarities between

Turing Machine and a General Purpose Computer, Definition and significant of Halting

Problem in Turing Machine.