## 15CS54 Automata Theory and Computability

Download VU CBCS notes of 15CS54 Automata Theory and Computability for 5th-semester computer science and engineering, VTU Belagavi.

### Module 1 – Introduction

Following are the contents of module 1 –

Why study Theory of Computation? Introduction to Strings andLanguages.

Finite State Machines (FSM): Deterministic FInite state machines, Regular languages, Designing Finite State Machines, Nondeterministic Finite State Machine.

From Finite State Machines to Operational Systems, Simulators for Finite State Machines, Minimizing Finite State Machines, a Canonical form of Regular Languages.

To download complete notes, click the below link

**Module 1 – 15CS54 Automata Theory and Computability**

### Module 2 – Regular Expressions (RE)

Following are the contents of module 2 – Regular Expressions (RE)

what is a Regular Expression? Kleene’s theorem, Applications of Regular Expressions, Manipulating and Simplifying Regular Expressions.

Definition of Regular Grammars and Regular languages. Regular and Nonregular Languages. Closure properties of Regular languages.

To download complete notes, click the below link

**Module 2 – 15CS54 Automata Theory and Computability**

### Module 3 – Context-Free Grammars (CFG)

Following are the contents of module 3 – Context-Free Grammars (CFG)

Introduction to Rewrite Systems, Grammars, CFGs, and languages. Designing Context-Free Grammars, simplifying Context-Free Grammars, proving that a Grammar is correct.

Definition of non-deterministic Pushdown Automata, Deterministic and Non-deterministic Pushdown Automatas, Non-determinism and Halting, alternative equivalent definitions of a Pushdown Automata, alternatives that are not equivalent to Pushdown Automata.

To download complete notes, click the below link

**Module 3 – 15CS54 Automata Theory and Computability**

### Module 4 – Context-Free and Non-Context-Free Languages

Following are the contents of module 4 – Context-Free and Non-Context-Free Languages

Where do the Context-Free Languages (CFL) fit, Showing a language is context-free, Pumping theorem for Context-Free Languages, Important closure properties of Context-Free Languages, Deterministic Context-Free Languages. Algorithms and Decision Procedures for Context-Free Languages.

Turing machine model, Representation, Language acceptability by Turing machine, design of Turing machine, Techniques for Turing machine construction.

To download complete notes, click the below link

**Module 4 – 15CS54 Automata Theory and Computability**

### Module 5 – Variants of Turing Machines (TM)

Following are the contents of module 5 – Variants of Turing Machines (TM)

Decidability: Definition of an algorithm, decidability, decidable languages. Undecidable languages, a halting problem of Turing Machines, Post correspondence problem and Complexity.

To download complete notes, click the below link

**Module 5 – 15CS54 Automata Theory and Computability**

If you like VTU CBCS notes, question papers, various study material, and for regular updates do like the facebook page.