JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Course Objectives:

• To introduce the fundamental concepts of formal languages, grammars and automata theory.
• Employ finite state machines to solve problems in computing.
• To understand the differences between decidability and undecidability.
• Introduce the major concepts of language translation and compiler design and impart the knowledge of practical skills necessary for constructing a compiler.

Course Outcomes:

• Able to employ finite state machines for modeling and solving computing problems.
• Able to design context free grammars for formal languages.
• Able to distinguish between decidability and undecidability
• Demonstrate the ability to design a compiler given a set of language features.
• Demonstrate the the knowledge of patterns & tokens for lexical analysis and Acquire skills in using lex tool l for developing a scanner and parser.

UNIT - I

Introduction to Finite Automata: Structural Representations, Automata and Complexity, the Central Concepts of Automata Theory – Alphabets, Strings, Languages, Problems. Nondeterministic Finite Automata: Formal Definition, an application, Text Search, Finite Automata with Epsilon-Transitions. Deterministic Finite Automata: Definition of DFA, How A DFA Process Strings, The language of DFA, Conversion of NFA with €-transitions to NFA without €-transitions. Conversion of NFA to DFA, Moore and Melay machines

UNIT - II

Regular Expressions: Finite Automata and Regular Expressions, Applications of Regular Expressions, Algebraic Laws for Regular Expressions, Conversion of Finite Automata to Regular Expressions. Context-Free Grammars: Definition of Context-Free Grammars, Derivations Using a Grammar, Leftmost and Rightmost Derivations, the Language of a Grammar, Parse Tress Push Down Automata: Definition of the Pushdown Automaton, the Languages of a PDA, Equivalence of PDA's and CFG's, Acceptance by final state, Acceptance by empty stack

UNIT - III

Normal Forms for Context- Free Grammars: Eliminating useless symbols, Eliminating €-Productions. Chomsky Normal form, Griebech Normal form Turing Machines: Introduction to Turing Machine, Formal Description of a Turing machine Undecidability: Introduction, Undecidable Problems about Turing Machines

UNIT - IV

Introduction: The structure of a compiler, the science of building a compiler, programming language basics Lexical Analysis: The Role of the Lexical Analyzer, Input Buffering, Recognition of Tokens, The Lexical Analyzer Generator Syntax Analysis: Introduction, Context-Free Grammars, Writing a Grammar, Top-Down Parsing, BottomUp Parsing

UNIT - V

Syntax-Directed Translation: Syntax-Directed Definitions, Evaluation Orders for SDD's Implementing L-Attributed SDD's. Intermediate-Code Generation: Variants of Syntax Trees, Three-Address Code Run-Time Environments: Stack Allocation of Space, Access to Nonlocal Data on the Stack

TEXT BOOKS:

• 1. Introduction to Automata Theory, Languages, and Computation, 3nd Edition, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Pearson Education.
• 2. Theory of Computer Science – Automata languages and computation, Mishra and Chandrashekaran, 2nd Edition, PHI.
• 3. Compilers: Principles, Techniques and Tools, Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffry D. Ullman, 2nd Edition, Pearson.

REFERENCE BOOKS:

• 1. Introduction to Languages and The Theory of Computation, John C Martin, TMH.
• 2. Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley.
• 3. A Text book on Automata Theory, P. K. Srimani, Nasir S. F. B, Cambridge University Press.
• 4. Introduction to the Theory of Computation, Michael Sipser, 3rd edition, Cengage Learning.
• 5. Introduction to Formal languages Automata Theory and Computation, Kamala Krithivasan, Rama R, Pearson.
• 6. lex & yacc – John R. Levine, Tony Mason, Doug Brown, O’reilly
• 7. Compiler Construction, Kenneth C. Louden, Thomson. Course Technology.