TOC Tutors

TOC Tutors :

Online | Offline Tutions for TOC

Visit http://www.learninggeeks.info for Registration. 

Call us @ 9718322472, 9810333483 

Mail us for any queries: learninggeeks@gmail.com

UNIT I AUTOMATA

Introduction to formal proof – Additional forms of proof – Inductive proofs –Finite Automata (FA) – Deterministic Finite Automata (DFA)– Non-deterministic Finite Automata (NFA) – Finite Automata with Epsilon transitions.

UNIT II REGULAR EXPRESSIONS AND LANGUAGES
Regular Expression – FA and Regular Expressions – Proving languages not to be regular – Closure properties of regular languages – Equivalence and minimization of Automata.

UNIT III CONTEXT-FREE GRAMMAR AND LANGUAGES

Context-Free Grammar (CFG) – Parse Trees – Ambiguity in grammars and languages – Definition of the Pushdown automata – Languages of a Pushdown Automata – Equivalence of Pushdown automata and CFG, Deterministic Pushdown Automata.

UNIT IV PROPERTIES OF CONTEXT-FREE LANGUAGES
Normal forms for CFG – Pumping Lemma for CFL - Closure Properties of CFL – Turing Machines – Programming Techniques for TM.

UNIT V TURING MACHINES
Turing Machines?Problems related to Turing Machines, Universal Turing Machines,Designing Turing Machines.

UNIT VI UNDECIDABILITY
A language that is not Recursively Enumerable (RE) – An undecidable problem that is RE – Undecidable problems about Turing Machine – Post’s Correspondence Problem - The classes P and NP.

Posted via web from learninggeeks's posterous