JNTUH B.Tech 2nd Year 2 sem Computer Science and Engineering R13 (2-2) Formal Languages and Automata Theory R13 syllabus.

JNTUH B.Tech 2nd year (2-2) Formal Languages and Automata Theory gives you detail information of Formal Languages and Automata Theory R13 syllabus It will be help full to understand you complete curriculum of the year.

Objectives

The purpose of this course is to acquaint the student with an overview of the theoretical foundations of computer science from the perspective of formal languages.

• Classify machines by their power to recognize languages.
• Employ finite state machines to solve problems in computing.
• Explain deterministic and non-deterministic machines.
• Comprehend the hierarchy of problems arising in the computer sciences.

UNIT I

Fundamentals : Strings, Alphabet, Language, Operations, Finite state machine, definitions, finite automaton model, acceptance of strings, and languages, deterministic finite automaton and non deterministic finite automaton, transition diagrams and Language recognizers.

Finite Automata : NFA with Î transitions – Significance, acceptance of languages. Conversions and Equivalence : Equivalence between NFA with and without Î transitions, NFA to DFA conversion, minimisation of FSM, equivalence between two FSM’s, Finite Automata with output- Moore and Melay machines.

UNIT II

Regular Languages : Regular sets, regular expressions, identity rules, Constructing finite Automata for a given regular expressions, Conversion of Finite Automata to Regular expressions. Pumping lemma of regular sets, closure properties of regular sets (proofs not required).

Grammar Formalism : Regular grammars-right linear and left linear grammars, equivalence between regular linear grammar and FA, inter conversion, Context free grammar, derivation trees, sentential forms. Right most and leftmost derivation of strings.

UNIT III 

Context Free Grammars : Ambiguity in context free grammars. Minimisation of Context Free Grammars. Chomsky normal form, Greiback normal form, Pumping Lemma for Context Free Languages. Enumeration of properties of CFL (proofs omitted).

Push Down Automata : Push down automata, definition, model, acceptance of CFL, Acceptance by final state and acceptance by empty state and its equivalence. Equivalence of CFL and PDA, interconversion. (Proofs not required). Introduction to DCFL and DPDA.

Download iStudy Android App for complete JNTUH syllabus, results, timetables and all other updates. There are no ads and no pdfs and will make your life way easier.

TEXT BOOKS 

• “Introduction to Automata Theory Languages and Computation”. Hopcroft H.E. and Ullman J. D. Pearson Education
• Introduction to Theory of Computation – Sipser 2nd edition Thomson

REFERENCES BOOKS

• Introduction to Forml languages Automata Theory and Computation Kamala Krithivasan Rama R.
• Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley.
• Theory Of Computation: A Problem – Solving Approach, Kavi Mahesh, Wiley India Pvt. Ltd.
• “Elements of Theory of Computation”, Lewis H.P. & Papadimition C.H. Pearson /PHI.
• Theory of Computer Science – Automata languages and computation -Mishra and Chandrashekaran, 2nd edition, PHI.

Outcomes

• Graduate should be able to understand the concept of abstract machines and their power to recognize the languages.
• Attains the knowledge of language classes & grammars relationship among them with the help of Chomsky hierarchy.
• Graduate will be able to understanding the pre-requisites to the course compiler or advanced compiler design.

For more information about all JNTU updates please stay connected to us on FB and don’t hesitate to ask any questions in the comment.