Rashtrasant Tukadoji Maharaj Nagpur University, Maharashtra, Artificial Intelligence 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

Unit - 1 Strings

Unit 1

Strings

1.1 Strings Alphabet Language operations Finite state machine definitions

1.2 Finite automation model

1.3 Acceptance of strings and language

1.4 Non deterministic finite automation

1.5 Deterministic finite automation

1.6 Equivalence between NFA and DFA

1.7 Conversion of NFA into DFA

1.8 Moore and Mealy machines

Unit 1

Strings

1.1 Strings Alphabet Language operations Finite state machine definitions

1.2 Finite automation model

1.3 Acceptance of strings and language

1.4 Non deterministic finite automation

1.5 Deterministic finite automation

1.6 Equivalence between NFA and DFA

1.7 Conversion of NFA into DFA

1.8 Moore and Mealy machines

Unit - 2 Regular sets

Unit 2

Regular sets

2.1 Regular sets

2.2 Regular expressions

2.3 Identity rules

2.4 Manipulation rules

2.5 Manipulation of regular expressions

2.6 Pumping lemma

2.7 Closure properties of regular sets

2.8 Chomsky hierarchy of languages

2.9 Regular Grammars Right linear and left linear grammars

2.10 Equivalence between regular linear programming and FA

Unit 2

Regular sets

2.1 Regular sets

2.2 Regular expressions

2.3 Identity rules

2.4 Manipulation rules

2.5 Manipulation of regular expressions

2.6 Pumping lemma

2.7 Closure properties of regular sets

2.8 Chomsky hierarchy of languages

2.9 Regular Grammars Right linear and left linear grammars

2.10 Equivalence between regular linear programming and FA

Unit - 3 Context free grammar

Unit 3

Context Free Grammar

3.1 Context Free Grammar

3.2 Derivation Trees

3.3 Chomsky normal form Greibach normal form

3.4 Push down automata Definition

3.5 Model acceptance of CFL

3.6 Equivalence of CFL and PDA Inter conversion

3.7 Closure properties of CFL

3.8 Pumping lemma for CFL

Unit 3

Context Free Grammar

3.1 Context Free Grammar

3.2 Derivation Trees

3.3 Chomsky normal form Greibach normal form

3.4 Push down automata Definition

3.5 Model acceptance of CFL

3.6 Equivalence of CFL and PDA Inter conversion

3.7 Closure properties of CFL

3.8 Pumping lemma for CFL

Unit - 4 Turing Machine

Unit 4

Turing Machine

4.1 Turing Machine Definition Model of TM

4.2 Design of TM

4.3 Universal Turing Machine

4.4 Computable function

4.5 Recursive enumerable language

4.6 Types of TM’s

4.7 Linear Bounded Automata

4.8 Context sensitive language

Unit 4

Turing Machine

4.1 Turing Machine Definition Model of TM

4.2 Design of TM

4.3 Universal Turing Machine

4.4 Computable function

4.5 Recursive enumerable language

4.6 Types of TM’s

4.7 Linear Bounded Automata

4.8 Context sensitive language

Unit - 5 Decidability and Undecidability of problems

Unit 5

Decidability and Undecidability of problems

5.1 Decidability and Undecidability of problems

5.2 Properties of recursive and recursively enumerable languages

5.3 Halting problems

5.4 Post correspondence problem

5.5 Ackerman function

5.6 Churchs’ hypothesis

5.7 Recursive and Primitive Functions

5.8 Bounded Minimization

5.9 Unbounded Minimization

Unit 5

Decidability and Undecidability of problems

5.1 Decidability and Undecidability of problems

5.2 Properties of recursive and recursively enumerable languages

5.3 Halting problems

5.4 Post correspondence problem

5.5 Ackerman function

5.6 Churchs’ hypothesis

5.7 Recursive and Primitive Functions

5.8 Bounded Minimization

5.9 Unbounded Minimization

Download AI Sem 4 syllabus pdf
Get access to 100s of MCQs, Question banks, notes and videos as per your syllabus.
Try Now for free
Other Subjects of Semester-4
Database management system
Microcontroller and embedded systems
Object oriented programming using java
Introduction to artificial intelligence
Mathematical foundations for artificial intelligence
Share  
Link Copied
More than 1 Million students use Goseeko! Join them to feel the power of smart learning.
Spot anything incorrect? Contact us