# Automata Theory And Computability

Semester : V

Course Code : 18CS54

CIE Marks : 40 SEE Marks : 60

## AUTOMATA THEORY AND COMPUTABILITY

18CS54

#### SYLLABUS

### Module-1

**Why study Theory of Computation, Languages and Strings:** Strings, Languages. A Language Hierarchy, Computation, **Finite State Machines (FSM):** Deterministic FSM, Regular languages, Designing FSM, Nondeterministic FSMs, From FSMs to Operational Systems, Simulators for FSMs, Minimizing FSMs, Canonical form of Regular languages, Finite State Transducers, Bidirectional Transducers.**Textbook 1: Ch 1,2, 3,4, 5.1 to 5.10**

### Module-2

**Regular Expressions (RE):** what is a RE?, Kleene‟s theorem, Applications of REs, Manipulating and Simplifying REs. Regular Grammars: Definition, Regular Grammars and Regular languages. Regular Languages (RL) and Non-regular Languages: How many RLs, To show that a language is regular, Closure properties of RLs, to show some languages are not RLs. **Textbook 1: Ch 6, 7, 8: 6.1 to 6.4, 7.1, 7.2, 8.1 to 8.4**

### Module-3

**Context-Free Grammars(CFG):** Introduction to Rewrite Systems and Grammars, CFGs and languages, designing CFGs, simplifying CFGs, proving that a Grammar is correct, Derivation and Parse trees, Ambiguity, Normal Forms. Pushdown Automata (PDA): Definition of non-deterministic PDA, Deterministic and Non-deterministic PDAs, Non-determinism and Halting, alternative equivalent definitions of a PDA, alternatives that are not equivalent to PDA.**Textbook 1: Ch 11, 12: 11.1 to 11.8, 12.1, 12.2, 12,4, 12.5, 12.6**

### Module-4

**Algorithms and Decision Procedures for CFLs:** Decidable questions, Un-decidable questions.** Turing Machine:** Turing machine model, Representation, Language acceptability by TM, design of TM, Techniques for TM construction. Variants of Turing Machines (TM), The model of Linear Bounded automata.**Textbook 1: Ch 14: 14.1, 14.2, Textbook 2: Ch 9.1 to 9.8**

### Module-5

**Decidability:** Definition of an algorithm, decidability, decidable languages, Undecidable languages, the halting problem of TM, Post correspondence problem. Complexity: Growth rate 08 of functions, the classes of P and NP, Quantum Computation: quantum computers, ChurchTuring thesis.** Applications:** G.1 Defining syntax of programming language, Appendix J: Security**Textbook 2: 10.1 to 10.7, 12.1, 12.2, 12.8, 12.8.1, 12.8.2**