CS60030: Formal Systems
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 | |||||||||||||||||
| |||||||||||||||||
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.