# 18CS54 Automata Theory and Computability

## 18CS54 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 and languages.

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.

### 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.

### 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 Automata, Non-determinism and Halting, alternative equivalent definitions of a Pushdown Automata, alternatives that are not equivalent to Pushdown Automata.

### 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.

### 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.

Click the below link to download the 2017 and 2015 Scheme VTU CBCS Notes of Automata Theory and Computability Notes

M-1, M-2, M-3, M-4 and M-5 another Set M-1 and M-2, M-3

Click the below link to download the 2018 Scheme VTU CBCS Notes of 18CS54 Automata Theory and Computability Notes

AUTOMATA THEORY AND COMPUTABILITY (18CS54) VTU CBCS Notes