Posts

Showing posts from January 2, 2011

Computer Engineering - Theory of Computation - Syllabus

GUJARAT TECHNOLOGICAL UNIVERSITY
B. E. SEMESTER: VI
Computer Engineering
Subject Name: Theory of Computation

Course Content:

Review Of Mathematical Terms And Theory:
Basic Mathematical Notations And Set Theory, Logic Functions And Relations, Language Definitions, Mathematical Inductions And Recursive Definitions

Finite Automata:
Deterministic And Non Deterministic Finite Automata, Ù-Transitions,Conversion From NFA To DFA, Kleene’s Theorem, Regular And Non Regular Languages

CFG (Context Free Grammar):
Introduction To CFG, CFG And Known Languages, Unions Concatenations And *’S Notations And CFL, Derivations Of Trees And Ambiguity, Unambiguous CFG And Algebric Expressions, Normal Forms And Siplified Forms

Pushdown Automata, CFL and NFL:
Introduction To PDA, Definition, DPDA, PDA Corresponding To CFG, CFG Corresponding To PDA, Introduction To CFL, Intersections And Complements Of CFL, Decisions Problems And CFL

Turing Machines, Recursive Language:
Model Of Computation And Church Turning Thesis,…