e-Learn @ SASTRA Back

Introduction to DFA

Introduction to DFA continued

NFA with epsilon moves to NFA without epsilon moves

Problem discussion

Problems continued

Regular expression to DFA with epsilon moves

DFA to regular expression

Closure properties of regular sets

Minimization of finite automata

Problems on minimization

Introduction to CFG

Regular grammar

Ambigous grammar

Elimination of useless symbols

Elimination of epsilon and unit productions

CYK Algorithm


Closure properties of context free languages

Pumping lemma for regular languages

Problems on Pumping lemma for regular languages

Problem solving

Push down Automaton

Deterministic and Non-deterministic PDA

Push down Automaton and Context free languages

PDA to CFL conversion

Problem solving

Turing machine

Designing a Turing machine for accepting a language

Designing a Turing machine for addition

Designing a Turing machine to multiply two positive integers

Chomsky Hierarchy

Primitive Recursive functions

Primitive Recursive functions(cont)

Polynomial time reduction

Recursive and recursively enumerable languages.

Unrestricted grammarand context sensitive grammar

Satisfiability problem


P,NP and NP complete

NP complete problems

Turing machine for multiplication

Theorem proving