Tuesday, October 31, 2017

GTU Syllabus

Review of Mathematical Theory: 
Sets, Functions, Logical statements,Proofs, relations, languages, Mathematical induction, strong principle,Recursive definitions

Regular Languages and Finite Automata: 
Regular expressions, regular languages, applications, Automata with output-Moore machine, Mealy machine, Finite automata, memory requirement in a recognizer, definition, union, intersection and complement of regular languages.Non Determinism Finite Automata, Conversion from NFA to FA, NULL- Non Determinism Finite Automata Conversion of NFA- NULL to NFA and equivalence of three Kleene’s Theorem, Minimization of Finite automata Regular And Non Regular Languages – pumping lemma

Context free grammar (CFG): 
Definition, Unions Concatenations And Kleen’s of Context free language Regular grammar, Derivations and Languages, Relationship between derivation and derivation trees, Ambiguity Unambiguous CFG and Algebraic Expressions BacosNaur Form (BNF), Normal Form – CNF

Pushdown Automata, CFL And NCFL: 
Definition, deterministic PDA, Equivalence of CFG and PDA, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL

Turing Machine (TM): 
TM Definition, Model Of Computation And Church Turning Thesis, computing functions with TM, Combining TM, Variations Of TM, Non Deterministic TM, Universal TM, Recursively and Enumerable Languages, Context sensitive languages and Chomsky hierarchy

Computable Functions: 
Partial, total, constant functions, Primitive Recursive Functions, Bounded Mineralization, Regular function, Recursive Functions