World Mentoring Academy "An Open Community for Successful Learning"

Free World class mobile education, earn a Bachelors for less than $5,000 books & Test Fees from State Universities, using Experiential, Design & Project based education. Supporting credit-by-exam & Challenging University courses.

Creative Commons License
Expand/collapse block About & Angel Club

$365 given2017 Join this project

Help $29 in treasury 

Expand/collapse block Login
Keep me logged in
Expand/collapse block Selected courses
Expand/collapse block Information for lesson "Theory of Computation, Theory of Automata, Formal Languages and Computation NPTEL CC-E"
Description: The objective of the course is to provide an exposition first to the notion of computability, then to the notion of computational feasibility or tractability. We first convince ourselves that for our purpose it suffices to consider only language recognition problems instead of general computational problems. We then provide a thorough account of finite state automata and regular languages, not only because these capture the simplest language class of interest and are useful in many diverse domains. But also because many fundamental notions like nondeterminism, proofs of impossibility, etc. get discussed at a conceptually very simple level. We then consider context grammars and languages, and their properties. Next, we consider Turing machines (TMs), show that as a model it is very robust, and the reasonableness of the Church-Turing hypothesis. After we realize TMs can work with (codes of) TMs as inputs, we obtain a universal TM.
Resources: OpenCourseware from NPTEL (India), Sheridan College, MIT, UC Berkeley, Stanford & many other of the World's finest University's.
Language: English
Professors: Michael Williams
Units: 42
Lesson content
Enroll Enroll