Master Theory of Computation: Models, Properties, and Equivalences

[heman]

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.

 

[neurocomp2003]

Its about how things are done on a computer...with a theoretical basis.
FSMs- are like graph theory...however each node represents a configuration or state of your environment. Each link from node to node represents how one goes from state to state. You write up a transition table normally to describe the FSM (eg current state, transition symbol/alphabet, new state). Simplest example is to create an ATM describe all the configurations or state, and the transitions are the button pressing. You'll learn the DFA and nDFA in class.

Grammars and regular expressions are the types of strings and grammaes that you can store on a computer. Minimality is the lowest # of states that a given FSM can be changed into(a transformation that makes it equivalent to the lowest).

Turing Machine or Tape: is the universal language...all languages and algorithms can be stored as a turing machine. Decidability is the process of deciding whether an algorithm will terminate. And Computability is the study if it can be done PvsNP(polynomial time or nonpolynomial). examples of NP are TSP-travelling salesman problem, boolean satisfiability, and some other various math like given a set of # {xi} can you find a subsum = n. Also if you prove one NP problem to be P or !P then the entire collection of NP problems will follow suit.

CFL: just various methods to store language/computer language. Like Parse trees...if you ever scripted in website language or computing language or a scripted for AI or openInventor...imagine how they store the commands