Anna University
Department of Computer Science Engineering and Information Technology
V Semester and VII Semester
Important Theorems
Semester: V
Year : 3rd Yr
Department : B.E Computer Science Engineering and B.Tech Information Technology
Regulation : 2008
Subject Code : CS2303
Subject Name : Theory of Computation
Contents : CS2303 Theory of Computation - Important Theorems.
CS2303 Theory of Computation
SOME OF THE
IMPORTANT THEOREMS AND PROOFS
1. Proof by
counter examples
2.
Inductive proofs – problems
Extended
del transition for NFA, DFA, sigma NFA
Language
accepted by DFA < = > NFA
Refer
Hopcroft book for below theorems
Pg : 77,
theorem 2.11
Pg : 78,
theorem 2.12
Theorem –
2.22, pg : 93
Theorem –
3.4, pg – 105
Pg – 116,
theorem – 3.7
Pumping
lemma for regular expression
Proof for
pumping lemma
Applications
for pumping lemma
Closure
properties of regular expression page: 140
Theorems:
5.12, 5.14, 5.16
Page - 199
– theorem
Applications
of CFG
PDA –
definition, instantaneous description of PDA
Page: 245 -
theorem - 6.9
Page: 248 -
theorem – 6.11
1st unit –
equivalent DFA and NFA, NFA with and without sigma transition
2nd unit –
DFA to regular expressions and regular expressions to DFA , pumping lemma ,
properties of regular expression
3rd unit –
refer above
Equivalent
of CFG to PDA and PDA to CFG, deterministic properties of CFG
CNF and GNF
- problem s and proofs
5th unit
Theorems
1.
Recursive language and recursive enumerable language
2. Decision
problems and undecidable problems examples
3.
Properties of recursive languages and recursive enumerable language
(4 theorems
– 16 marks) (in boxes they will give )
4. Define
diagonal language
5.
Universal language – based theorems
6. Rice
theorems
7. PN and
NP problems
8. Samples
for NP problems
9. NP –
complete, NP – hard
Sample NP -
complete and NP – hard problems
10. Binary
equivalent of following integers is stored in a tape
Multiply
the following by 2
(11 x 12 =
1100)
(100 x 10 =
1000)
11. Define
diagonal language
12. Define
the language LU and show that
LU is
recursively enumerable but not recursive
13.
Multiple track TM and multiple tape TM difference
14. Minimum
no of stacks to represent a TM and for PDA
15. Count
down M/C
16.
Properties of CFL, properties of regular language
17. Final
stack , empty stack – 2 theorems and proof of it
18. CFG –
equivalent PDA - proof and theorems
19. PDA ?
CFG ( theorem )
20. Pumping
lemma – proof – 8 marks for CFL and regular language, problems( 4m / 2m )
