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