EE-Learning
PROBLEMS AND SOLUTIONS – III
Catogry:
Computing
Subject:
Computer Science
Course:
Theory Of Computation I
Lecture List
NP – COMPLETE PROBLEMS (Contd)
MEMBRANE COMPUTING
REGULATED REWRITING
POST’S CORRESPONDENCE PROBLEMS
NP – COMPLETE PROBLEMS , COOK’S THEOREM
POST’S CORRESPONDENCE PROBLEMS (Contd) TIME AND TAPE COMPLEXITY OT TM
L – SYSTEMS
GRAMMAR SYSTEMS
DNA COMPUTING
PROBLEMS AND INSTANCES , UNIVERSAL TM , DECIDABILITY
RICE’S THEOREM,LINEAR BOUNDED AUTOMATA,PROPERTIES OF TM
RECURSIVE SETS , RECURSIVELY INNUMERABLE SETS , ENCODING OF TM , HALTING PROBLEM
TURING MACHINE AS A GENERATING DEVICE
GENERALIZED VERSIONS OF TURING MACHINES
TURING MACHINE AS ACCEPTOR , TECHNIQUES FOR TM CONSTRUCTION
TURING MACHINES (Contd)
TURING MACHINES
PROBLEMS AND SOLUTIONS – III
PROBLEMS AND SOLUTIONS-I
PUSHDOWN AUTOMATA PDA TO CFG
PUSHDOWN AUTOMATA CFG TO PDA
PUSHDOWN AUTOMATA,EQUIVALENCE BETWEEN ACCEPTANCE BY EMPTY STORE
PUSHDOWN AUTOMATA
FSA WITH OUTPUT MOORE AND MEALY MACHINES
MINIMIZATION OF DFSA
MYHILL-NERODE THEOREM
PUMPING LEMMAS FOR REGULAR SETS AND CFL
PROBLEMS AND SOLUTIONS
DFSA TO REGULAR EXPRESSIONS
REGULAR EXPRESSIONS , REGULAR EXPRESSIONS TO NFSA
EQUIVALENCE BETWEEN FSA AND TYPE 3 GRAMMARS
NON DETERMINISTIC FSA WITH E(Epsilon)- MOVES
NON DETERMINISTIC FSA (Contd)
NON-DETERMINISTIC FSA
FINAL STATE AUTOMATA
GREIBACH NORMAL FORM FOR CFG
REMOVAL OF UNIT PRODUCTIONS , CHOMSKY NORMAL FORM FOR CFG
SIMPLICATION OF CFG
AMBIGUITY IN CFG
GRAMMARS AND LANGUAGES GENERATED (Contd)
GRAMMARS AND LANGUAGES GENERATED
GRAMMARS AND NATURAL LANGUAGE PROCESSING