Scribd Logo
Upload

Welcome to Scribd!

  • 61 views

    II Year Syllabus 2016 Regulation

    Uploaded by

    jani28cse
    This document outlines the course objectives and content for a course on Formal Language and Automata Theory. The course covers topics such as finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and computability. The six units cover these topics and their applications. The objectives are to introduce students to the concepts of computation theory and the relationships between formal languages, grammars, and automata. Students will learn to classify machines by their computational power and apply concepts like finite state machines to computing problems.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd

    II Year Syllabus 2016 Regulation

    Uploaded by

    jani28cse
    61 views2 pages
    This document outlines the course objectives and content for a course on Formal Language and Automata Theory. The course covers topics such as finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and computability. The six units cover these topics and their applications. The objectives are to introduce students to the concepts of computation theory and the relationships between formal languages, grammars, and automata. Students will learn to classify machines by their computational power and apply concepts like finite state machines to computing problems.

    Original Description:

    JNTUK SYLLABUS

    Copyright

    © © All Rights Reserved

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document outlines the course objectives and content for a course on Formal Language and Automata Theory. The course covers topics such as finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and computability. The six units cover these topics and their applications. The objectives are to introduce students to the concepts of computation theory and the relationships between formal languages, grammars, and automata. Students will learn to classify machines by their computational power and apply concepts like finite state machines to computing problems.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    61 views2 pages

    II Year Syllabus 2016 Regulation

    Uploaded by

    jani28cse
    This document outlines the course objectives and content for a course on Formal Language and Automata Theory. The course covers topics such as finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and computability. The six units cover these topics and their applications. The objectives are to introduce students to the concepts of computation theory and the relationships between formal languages, grammars, and automata. Students will learn to classify machines by their computational power and apply concepts like finite state machines to computing problems.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 2

    II Year – II Semester LTPC

    4003

    FORMAL LANGUAGE AND AUTOMATA THEORY


    OBJECTIVE:
    1.Introduce the student to the concepts of Theory of computation in computer science
    2.The students should acquire insights into the relationship among formal languages, formal
    Grammars and automat.
    UNIT – I: Finite Automata
    Why Study Automata Theory? The Central Concepts of Automata Theory, Automation, Finite
    Automation, Transition Systems, Acceptance of a String by a Finite Automation, DFA, Design of DFAs,
    NFA, Design of NFA, Equivalence of DFA and NFA, Conversion of NFA into DFA, Finite Automata with E-
    Transition, Minimization of Finite Automata, Mealy and Moore
    Machines, Applications and Limitation of Finite Automata.
    UNIT – II: Regular Expressions
    Regular Expressions, Regular Sets, Identity Rules, Equivalence of two Regular Expressions,
    Manipulations of Regular Expressions, Finite Automata, and Regular Expressions, Inter
    Conversion, Equivalence between Finite Automata and Regular Expressions, Pumping Lemma, Closers
    Properties, Applications of Regular Expressions, Finite Automata and Regular Grammars, Regular
    Expressions and Regular Grammars.
    UNIT – III: Context Free Grammars
    Formal Languages, Grammars, Classification of Grammars, Chomsky Hierarchy Theorem,
    Context Free Grammar, Leftmost and Rightmost Derivations, Parse Trees, Ambiguous
    Grammars, Simplification of Context Free Grammars-Elimination of Useless Symbols, EProductions and
    Unit Productions, Normal Forms for Context Free Grammars-Chomsky Normal Form and Greibach
    Normal Form, Pumping Lemma, Closure Properties, applications of Context Free Grammars.
    UNIT – IV: Pushdown Automata
    Pushdown Automata, Definition, Model, Graphical Notation, Instantaneous Description
    Language Acceptance of pushdown Automata, Design of Pushdown Automata, Deterministic and Non –
    Deterministic Pushdown Automata, Equivalence of Pushdown Automata and Context Free Grammars
    Conversion, Two Stack Pushdown Automata, Application of Pushdown Automata.
    UNIT – V: Turning Machine
    Turing Machine, Definition, Model, Representation of Turing Machines-Instantaneous
    Descriptions, Transition Tables and Transition Diagrams, Language of a Turing Machine,
    Design of Turing Machines, Techniques for Turing Machine Construction, Types of Turing
    Machines, Church’s Thesis, Universal Turing Machine, Restricted Turing Machine.
    UNIT – VI: Computability
    Decidable and Un-decidable Problems, Halting Problem of Turing Machines, Post’s
    Correspondence Problem, Modified Post’s Correspondence Problem, Classes of P and NP, NPHard
    and NP-Complete Problems.
    OUTCOMES:
    • 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 science
    TEXT BOOKS:
    1. Introduction to Automata Theory, Languages and Computation, J.E.Hopcroft, R.Motwani and
    J.D.Ullman, 3rd Edition, Pearson, 2008.
    2. Theory of Computer Science-Automata, Languages and Computation, K.L.P.Mishra and
    N.Chandrasekharan, 3rd Edition, PHI, 2007.
    REFERENCE BOOKS:
    1. Formal Language and Automata Theory, K.V.N.Sunitha and N.Kalyani, Pearson, 2015.
    2. Introduction to Automata Theory, Formal Languages and Computation, Shyamalendu Kandar,
    Pearson, 2013.
    3. Theory of Computation, V.Kulkarni, Oxford University Press, 2013.
    4. Theory of Automata, Languages and Computation, Rajendra Kumar, McGraw Hill, 2014.

    You might also like