Book Details

Formal Languages and Automata Theory

Formal Languages and Automata Theory

Published by uLektz

Course Code : R162216
Author : uLektz
University : JNTU Kakinada
Regulation : 2016
Categories : Computer Science
Format : ico_bookePUB3 (DRM Protected)
Type : eBook

FREE

Buy Now

Description :Formal Languages and Automata Theory of R162216 covers the latest syllabus prescribed by JNTU Kakinada for regulation 2016. Author: uLektz, Published by uLektz Learning Solutions Private Limited.

Note : No printed book. Only ebook. Access eBook using uLektz apps for Android, iOS and Windows Desktop PC.

Topics
UNIT I FINITE AUTOMATA

1.1 Why Study Automata Theory?, The Central Concepts of Automata Theory

1.2 Automation, Finite Automation

1.3 Transition Systems

1.4 Acceptance of a String by a Finite Automation

1.5 DFA, Design of DFAs, NFA, Design of NFA, Equivalence of DFA and NFA, Conversion of NFA into DFA

1.6 Finite Automata with Ɛ-Transition

1.7 Minimization of Finite Automata

1.8 Mealy and Moore Machines, Applications and Limitation of Finite Automata

UNIT II REGULAR EXPRESSIONS

2.1 Regular Expressions, Regular Sets, Identity Rules

2.2 Equivalence of two Regular Expressions, Manipulations of Regular Expressions, Finite Automata and Regular Expressions, Inter Conversion, Equivalence between Finite Automata and Regular Expressions

2.3 Pumping Lemma

2.4 Closers Properties, Applications of Regular Expressions

2.5 Finite Automata and Regular Grammars, Regular Expressions and Regular Grammars

UNIT III CONTEXT FREE GRAMMARS

3.1 Formal Languages, Grammars, Classification of Grammars, Chomsky Hierarchy Theorem

3.2 Context Free Grammar

3.3 Leftmost and Rightmost Derivations

3.4 Parse Trees

3.5 Ambiguous Grammars

3.6 Simplification of Context Free Grammars, Elimination of Useless Symbols, ε-productions and Unit Productions

3.7 Normal Forms for Context Free Grammars, Chomsky normal form, Greibach Normal form

3.8 Pumping Lemma

3.9 Closure Properties, Applications of Context Free Grammars

UNIT IV PUSHDOWN AUTOMATA

4.1 Pushdown Automata, Definition, Model, Graphical Notation, Instantaneous Description Language Acceptance of pushdown Automata

4.2 Design of Pushdown Automata

4.3 Deterministic and Non - Deterministic Pushdown Automata, Equivalence of Pushdown Automata and Context Free Grammars Conversion

4.4 Two Stack Pushdown Automata, Application of Pushdown Automata

UNIT V TURNING MACHINE

5.1 Turing Machine, Definition, Model

5.2 Representation of Turing Machines-Instantaneous Descriptions, Transition Tables and Transition Diagrams

5.3 Language of a Turing Machine

5.4 Design of Turing Machines

5.5 Techniques for Turing Machine Construction

5.6 Types of Turing Machines

5.7 Church’s Thesis

5.8 Universal Turing Machine, Restricted Turing Machine

UNIT VI COMPUTABILITY

6.1 Decidable and Un-decidable Problems

6.2 Post’s Correspondence Problem, Modified Post Correspondence Problem (MPCP)

6.3 Classes of P and NP, NP-Hard and NP-Complete Problems

loading