Theory Of Computations syllabus

Derived reading outline. Source text split at semicolons, line breaks and sentence boundaries, not an official topic hierarchy.

• Basic Concepts: Finite and infinite set, Symbols, Strings : Empty String, Substring of a string, Concatenation of strings, Language :Formal Language Definition, Finite representation of languages , Operations on languages: Union, Concatenation, Kleene star and Kleene plus, Concept of Basic Machine.
• FA without output: Finite State Machines(FSM), Deterministic and Nondeterministic FA( DFA & NFA), epsilon NFA, Conversion of NFA with epsilon moves to NFA, Conversion of NFA to DFA, and Conversion of NFA with epsilon moves to DFA, Minimization of DFAs.
• FA with output: Moore and Mealy machines - Definition, Construction, Inter- Conversion.
• Case Study: FSM for vending Machine, Spell checker, Finite Automata in ATM PIN Validation System

Derived reading outline. Source text split at semicolons, line breaks and sentence boundaries, not an official topic hierarchy.

• Introduction, Operators of RE, Precedence of operators, Algebraic laws for RE, Language to Regular Expressions, Equivalence of two REs, Kleene’s theorem.
• Conversions: RE to NFA, DFA, DFA to RE using Arden’s theorem, Pumping Lemma for Regular languages, Closure(union, intersection, complementation, concatenation, Kleene closure) and Decision properties of Regular languages( Membership, Emptiness,Finiteness and Infiniteness) The Myhill–Nerode Theorem Case Study: RE for variable name validation, RE to match a specific word from given string ,Regular Expressions in Email Validation System

Derived reading outline. Source text split at semicolons, line breaks and sentence boundaries, not an official topic hierarchy.

• Formal Definition of Context Free Grammar, Sentential form, Derivation and Derivation Tree/ Parse Tree, Context Free Language (CFL), Ambiguous Grammar, writing grammar for language, Simplification of CFG: Eliminating ™-productions, unit productions, useless production, useless symbols, and Normal Forms- Chomsky normal form, Greibach normal form, Pumping Lemma for CFG, Closure properties of CFL, Chomsky Hierarchy, Applications of CFG:-Palindromes, Parenthesis Match ,Parser, Markup languages, XML and Document Type Definitions.
• Case Study: Grammar Design for Arithmetic Expressions, Designing a Grammar for a Simple Programming Language Construct

Derived reading outline. Source text split at semicolons, line breaks and sentence boundaries, not an official topic hierarchy.

• Introduction, Formal definition of PDA, Equivalence of Acceptance by Final State & Empty stack, Non-deterministic PDA (NPDA), PDA & Context Free Language, Equivalence of PDA and CFG, PDA vs CFLs.
• Applications of PDA,Introduction to Post Machine, Case Study: Applying PDA for Top-Down Parsing, Bottom-up Parsing Pushdown Automata (PDA) in Compiler Syntax Checking,XML / HTML Tag Validation

Derived reading outline. Source text split at semicolons, line breaks and sentence boundaries, not an official topic hierarchy.

• Turing machine (TMs): Basic model, definition, and representation, TM Instantaneous Description, Transition Function, Language accepted TM, Deterministic Turing Machines (DTM), and Construction of DTM.
• Universal Turing Machine (UTM), Church-Turing hypothesis, Comparison between FA, PDA and TM.
• Turing Machine Halting Problem.
• Decidable Problems and Undecidable Problems, Church-Turing Thesis.
• Reducibility: Undecidable Problems that are recursively enumerable, A Simple Undecidable.
• Complexity Classes: Time and Space Measures, The Class P, Examples of problems in P, The Class NP, Examples of problems in NP, P Problem Versus NP Problem, NP-completeness and hard Problems.
• Case Study: Application of Turing Machine for Language Recognition, Comparative Study of Variants of Turing Machines, Analysis of the Halting Problem