Other university, Computer Engineering , 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 Formal Language Theory And Finite Automata

Unit 1

Formal Language Theory and Finite Automata

1.1 Finite Automata FA An informal picture of FA

1.2 Finite State Machine FSM

1.3 Language accepted by FA

1.4 Definition of Regular Language

1.5 FA without output Deterministic and Nondeterministic FA DFA and NFA

1.6 Epsilon NFA and interconversion

1.7 Minimization of DFAs

1.8 FA with output Moore and Mealy machines Definition models interconversion

Unit - 2 Regular Expressions (RE)

Unit 2

Regular Expressions RE

2.1 Introduction

2.2 Operators of RE Precedence of operators

2.3 Algebraic laws for RE

2.4 Language to Regular Expressions Equivalence of two REs

2.5 Conversions RE to NFA DFA DFA to RE using Arden’s theorem

2.6 Pumping Lemma for Regular languages

2.7 Closure and Decision properties of Regular languages

2.8 MyhillNerode theorem

Unit - 3 Context Free Grammar (CFG) And Context Free Language(CFL)

Unit 3

Context Free Grammar CFG and Context Free Language CFL

3.1 Basic Elements of Grammar

3.2 Formal Definition of Context Free Grammar

3.3 Sentential form

3.4 Derivation and Derivation Tree Parse Tree

3.5 Context Free Language CFL

3.6 Ambiguous Grammar

3.7 Writing grammar for language

3.8 Simplification of CFG Eliminating Єproductions

3.9 Unit productions

3.10 Useless production and useless symbols

3.11 Normal Forms Chomsky Normal Form Greibach Normal Form

3.12 Pumping Lemma for CFG

3.13 Closure properties of CFL

3.14 Decision properties of CFL

3.15 Chomsky Hierarchy

3.16 CockYoungerKasami Algorithm

Unit - 4 Pushdown Automata (PDA)

Unit 4

Pushdown Automata PDA

4.1 Introduction Formal definition of PDA

4.2 Equivalence of Acceptance by Final State and Empty stack

4.3 Nondeterministic PDA NPDA

4.4 PDA and Context Free Language

4.5 Equivalence of PDA and CFG

4.6 PDA vs CFLs

4.7 Deterministic CFLs

Unit - 5 Turing Machines (TM)

Unit 5

Turing Machines TM

5.1 Turing Machine Model Formal definition of Turing Machines

5.2 Language Acceptability by Turing Machines

5.3 Design of TM Description of TM

5.4 Techniques for TM Construction

5.5 Computing function with Turing Machine

5.6 Variants of Turing Machines

5.7 Halting Problem of TM Halting vs Looping

5.8 A Turingunrecognizable language

5.9 Reducibility Recursion Theorem

5.10 The Model of Linear Bounded Automata

Unit - 6 Computability And Complexity Theory

Unit 6

Computability and Complexity Theory

6.1 Computability Theory Decidable Problems and Undecidable Problems

6.2 ChurchTuring Thesis

6.3 Reducibility Undecidable Problems that is recursively enumerable

6.4 A Simple Undecidable problem

6.5 Complexity Classes Time and Space Measures

6.6 The Class P Examples of problems in P The Class NP Examples of problems in NP P Problem Versus NP Problem NPcompleteness and NPhard Problems

6.7 Case study on Travelling salesman problem

Download CSE Third Year syllabus pdf
Get access to 100s of MCQs, Question banks, notes and videos as per your syllabus.
Try Now for free
Other Subjects of third-year
Compiler design
Machine learning
Computer networks
Software engineering
Artificial intelligence
Advance java programming
Database management systems
Popular posts
Top 10 free online resources to learn coding
What is machine learning
What is cloud computing
What is DBMS architecture
Sorting algorithm overview
Share  
Link Copied
More than 1 Million students use Goseeko! Join them to feel the power of smart learning.
Spot anything incorrect? Contact us