__AUTOMATA THEORY AND COMPUTABILITY__

__AUTOMATA THEORY AND COMPUTABILITY__

__Course Code:18CS54 __

CIE Marks:40

SEE Marks:60

Number of Contact Hours/Week:3:0:0

Total Number of Contact Hours:40

Exam Hours:03

CREDITS:3

CIE Marks:40

SEE Marks:60

Number of Contact Hours/Week:3:0:0

Total Number of Contact Hours:40

Exam Hours:03

CREDITS:3

__Course Learning Objectives: This course (18CS54) will enable students to:__

• Introduce core concepts in Automata and Theory of Computation• Identify different Formal language Classes and their Relationships

• Design Grammars and Recognizers for different formal languages

• Prove or disprove theorems in automata theory using their properties

• Determine the decidability and intractability of Computational problems

__Module 1__

Why study the Theory of Computation, Languages and Strings: Strings, Languages. ALanguage 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

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, Nondeterminism

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

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, CFGsand 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, Nondeterminism

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-decidablequestions. 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, Undecidablelanguages, halting problem of TM, Post correspondence problem. Complexity: Growth rate

08

of functions, the classes of P and NP, Quantum Computation: quantum computers, Church-

Turing 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

Textbook 1: Appendix: G.1(only), J.1 & J.2

__Course Outcomes: The student will be able to :__

• Acquire fundamental understanding of the core concepts in automata theory and Theory of Computation• Learn how to translate between different models of Computation (e.g., Deterministic and Non-deterministic and Software models).

• Design Grammars and Automata (recognizers) for different language classes and become knowledgeable about restricted models of Computation (Regular, Context Free) and their relative powers.

• Develop skills in formal reasoning and reduction of a problem to a formal model, with an emphasis on semantic precision and conciseness.

• Classify a problem with respect to different models of Computation.

Full Notes |

__Question Paper Pattern:__

• The question paper will have ten questions.• Each full Question consisting of 20 marks

• There will be 2 full questions (with a maximum of four sub questions) from each module.

• Each full question will have sub questions covering all the topics under a module.

• The students will have to answer 5 full questions, selecting one full question from each module.

__Textbooks:__

1. Elaine Rich, Automata, Computability and Complexity, 1st Edition, Pearson education,2012/20132. K L P Mishra, N Chandrasekaran , 3rd Edition, Theory of Computer Science, PhI, 2012.

__Reference Books:__

1. John E Hopcroft, Rajeev Motwani, Jeffery D Ullman, Introduction to AutomataTheory, Languages, and Computation, 3rd Edition, Pearson Education, 20132. Michael Sipser : Introduction to the Theory of Computation, 3rd edition, Cengage learning,2013

3. John C Martin, Introduction to Languages and The Theory of Computation, 3rd Edition, Tata McGraw –Hill Publishing Company Limited, 2013

4. Peter Linz, “An Introduction to Formal Languages and Automata”, 3rd Edition, Narosa Publishers, 1998

5. Basavaraj S. Anami, Karibasappa K G, Formal Languages and Automata theory, Wiley India, 2012

6. C K Nagpal, Formal Languages and Automata Theory, Oxford University press, 2012.

Faculty can utilize open source tools (like JFLAP) to make teaching and learning more interactive.