Become a data analyst in the next 4 months and kickstart your career. 100% placement assistance. Start your Analytics journey with our free Python course.
Rashtrasant Tukadoji Maharaj Nagpur University, Maharashtra, Computer Engineering Semester 4, Theory of Computation Syllabus
Theory of Computation Lecture notes | Videos | Free pdf Download | Previous years solved question papers | MCQs | Question Banks| Syllabus
Get access to 100s of MCQs, Question banks, notes and videos as per your syllabus.
Try Now for free
Try Now for free
Unit - 1 Finite Automata
Unit 1
Finite Automata
1.1 Finite Automata FA Basic terminology and Definitions
1.2 Chomsky hierarchy
1.3 Deterministic Finite Automata
1.4 Language of DFA
1.5 Nondeterministic Finite Automata
1.6 Equivalence of Deterministic and Nondeterministic Finite Automata
1.7 Application of Finite Automata
1.8 Finite Automata with Epsilon Transition
1.9 Eliminating Epsilon transition
1.10 Minimization of Deterministic Finite Automata
1.11 Finite automata with output Moore and Mealy machines and Inter conversion
Unit - 2 Regular Grammars
Unit 2
Regular Grammars and Regular Expressions
2.1 Regular Grammars RG Definition
2.2 Regular grammar and FA conversion
2.3 Proving language to be nonregular
2.4 Pumping lemma Applications
2.5 Closure properties of regular language
2.6 Regular Expression RE Introduction
2.7 Identities of Regular Expressions
2.8 Finite Automata and Regular Expressions
2.9 Converting from DFA’s to Regular Expressions
2.10 Converting Regular Expressions to Automata
2.11 Application of Regular Expressions
Regular Grammar and Regular Expressions
Unit 2
Regular Grammars and Regular Expressions
2.1 Regular Grammars RG Definition
2.2 Regular grammar and FA conversion
2.3 Proving language to be nonregular
2.4 Pumping lemma Applications
2.5 Closure properties of regular language
2.6 Regular Expression RE Introduction
2.7 Identities of Regular Expressions
2.8 Finite Automata and Regular Expressions
Unit 2
Regular Grammars and Regular Expressions
2.1 Regular Grammars RG Definition
2.2 Regular grammar and FA conversion
2.3 Proving language to be nonregular
2.4 Pumping lemma Applications
2.5 Closure properties of regular language
2.6 Regular Expression RE Introduction
2.7 Identities of Regular Expressions
2.8 Finite Automata and Regular Expressions
2.9 Converting from DFA’s to Regular Expressions
2.10 Converting Regular Expressions to Automata
2.11 Application of Regular Expressions
Unit 2
Regular Grammars and Regular Expressions
2.1 Regular Grammars RG Definition
2.2 Regular grammar and FA conversion
2.3 Proving language to be nonregular
2.4 Pumping lemma Applications
2.5 Closure properties of regular language
2.6 Regular Expression RE Introduction
2.7 Identities of Regular Expressions
2.8 Finite Automata and Regular Expressions
2.9 Converting from DFA’s to Regular Expressions
2.10 Converting Regular Expressions to Automata
2.11 Application of Regular Expressions
Unit - 3 Context Free Grammar
Unit 3
Context Free Grammar
3.1 Context Free Grammar CFG Definition
3.2 Parse Trees
3.3 Derivation Trees Rightmost and Leftmost derivations of strings and conversions
3.4 Ambiguity in CFGs
3.5 Minimization of CFGs
3.6 Normal forms for CFG
3.7 Pumping lemma for CFLs
Unit 3
Context Free Grammar
3.1 Context Free Grammar CFG Definition
Unit 3
Context Free Grammar
3.1 Context Free Grammar CFG Definition
3.2 Parse Trees
3.3 Derivation Trees Rightmost and Leftmost derivations of strings and conversions
3.4 Ambiguity in CFGs
3.5 Minimization of CFGs
3.6 Normal forms for CFG
3.7 Pumping lemma for CFLs
Unit - 4 Push down Automata
Unit 4
Push Down Automata
4.1 Push Down Automata PDA Definition Model
4.2 Nondeterminism
4.3 Acceptance by two methods and their equivalence
4.4 Conversion of PDA to CFG CFG to PDAs
4.5 Closure and decision properties of CFLs
Unit 4
Push Down Automata
4.1 Push Down Automata PDA Definition Model
4.2 Nondeterminism
4.3 Acceptance by two methods and their equivalence
4.4 Conversion of PDA to CFG CFG to PDAs
4.5 Closure and decision properties of CFLs
Push Down Automata
Unit 4
Push Down Automata
4.1 Push Down Automata PDA Definition Model
4.2 Nondeterminism
4.3 Acceptance by two methods and their equivalence
4.4 Conversion of PDA to CFG CFG to PDAs
4.5 Closure and decision properties of CFLs
Unit - 5 Turing Machines
Unit 5
Turing Machine
5.1 Turing Machine TM Formal definition and behavior
5.2 Language of a TM TM as acceptor
5.3 TM as transducer
5.4 Variations of TM
5.5 Linear Bounded Automata
5.6 TM as computer of function
5.7 Properties of recursive and recursively enumerable languages
5.8 Recursively enumerable set
5.9 Undesirability
5.10 Decidability and solvability
5.11 Post correspondence problem
5.12 Primitive recursive functions
5.13 Ackermann function
Unit 5
Turing Machine
5.1 Turing Machine TM Formal definition and behavior
5.2 Language of a TM TM as acceptor
5.3 TM as transducer
5.4 Variations of TM
5.5 Linear Bounded Automata
5.6 TM as computer of function
5.7 Properties of recursive and recursively enumerable languages
5.8 Recursively enumerable set
5.9 Undesirability
5.10 Decidability and solvability
5.11 Post correspondence problem
5.12 Primitive recursive functions
5.13 Ackermann function
Unit 5
Turing Machine
5.1 Turing Machine TM Formal definition and behavior
5.2 Language of a TM TM as acceptor
5.3 TM as transducer
5.4 Variations of TM
5.5 Linear Bounded Automata
5.6 TM as computer of function
5.7 Properties of recursive and recursively enumerable languages
Unit 5
Turing Machine
5.1 Turing Machine TM Formal definition and behavior
5.2 Language of a TM TM as acceptor
5.3 TM as transducer
5.4 Variations of TM
5.5 Linear Bounded Automata
5.6 TM as computer of function
5.7 Properties of recursive and recursively enumerable languages
5.8 Recursively enumerable set
5.9 Undesirability
5.10 Decidability and solvability
5.11 Post correspondence problem
5.12 Primitive recursive functions
5.13 Ackermann function
Download CSE Sem 4 syllabus pdf
Get access to 100s of MCQs, Question banks, notes and videos as per your syllabus.
Try Now for free
Try Now for free
Other Subjects of Semester-2
Share
Link Copied
More than 1 Million students use Goseeko! Join them to feel the power of smart learning.
Spot anything incorrect? Contact us
Goseeko covers the entire spectrum of student’s journey from Academics to Career. From helping them to ace their academics with our personalized study material to providing them with career development resources, our students meet their academic and professional goals.
Courses
B.E.
B.Com
B.A.
BBA
BMS
BSC
Resources
Notes
MCQ
Question bank
Audio bites
Express Class
Reference Videos
Solved Question Papers
