- #1
heman
- 361
- 0
I am taking this course this semester and i don't have enough idea about what this is all about...like i want to have a clearcut view in mind like how this coyrse helps...please i appreciate your comments..
Syllabus runs as::
Theory of Computation
Course Contents:
Models of computation -- classification, properties and equivalences.
Regular languages models: finite state machines (deterministic and non-deterministic), regular grammars, regular expressions, equivalence of deterministic and non-deterministic machines and of the three models. Properties: closure, decidability, minimality of automata, iteration theorems.
Recursive and recursively enumerable sets models: turing machines, grammars, recursive functions, their equivalence. Church's thesis. Properties: closure, decidability, undecidablity/non-computability, notion of reductions.
Context-free languages models: grammars (including different normal forms), pushdown automata, and their equivalence. Properties: closure, iteration theorems, parsing.
Syllabus runs as::
Theory of Computation
Course Contents:
Models of computation -- classification, properties and equivalences.
Regular languages models: finite state machines (deterministic and non-deterministic), regular grammars, regular expressions, equivalence of deterministic and non-deterministic machines and of the three models. Properties: closure, decidability, minimality of automata, iteration theorems.
Recursive and recursively enumerable sets models: turing machines, grammars, recursive functions, their equivalence. Church's thesis. Properties: closure, decidability, undecidablity/non-computability, notion of reductions.
Context-free languages models: grammars (including different normal forms), pushdown automata, and their equivalence. Properties: closure, iteration theorems, parsing.