I am taking this course this semester and i dont have enough idea about what this is all about...like i wanna have a clearcut view in mind like how this coyrse helps...please i appreciate your comments..(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Theory of computation

**Physics Forums | Science Articles, Homework Help, Discussion**