CS60030: Formal Systems

From Metakgp Wiki
Jump to navigation Jump to search
CS60030
Course name Formal Systems
Offered by Computer Science & Engineering
Credits 4
L-T-P 3-1-0
Previous Year Grade Distribution


2






EX A B C D P F
Semester Spring


Syllabus

Syllabus mentioned in ERP

Formal languages and their related automata, Turing machines, type-0 languages,linear bounded automata and CSLs. Time and tape bounded Turing machines, timeand space bounds for recognizing CFLs. Turing Computability: number theoreticcomputations by Turing machines and indexing. Axiomatic systems, their soundnessand completeness. Recursive function theory: primitive recursive functions andprimitive recursive predicates. Ackermanns function, recursive and general recursivefunctions. Computability and decidability: computable functions, computable sets,decision problems. Fixpoint theory of programs, functions and functionals,verification methods, Lambda calculus and applications.


Concepts taught in class

Student Opinion

How to Crack the Paper

Classroom resources

Additional Resources