Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    20BS1403

    Uploaded by

    20501a05b9
    This document outlines the academic rules and regulations for a course on Formal Languages and Automata Theory. It includes information on course code, category, credits, prerequisites, outcomes, syllabus, and learning resources.

    Copyright:

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

    20BS1403

    Uploaded by

    20501a05b9
    4 views2 pages
    This document outlines the academic rules and regulations for a course on Formal Languages and Automata Theory. It includes information on course code, category, credits, prerequisites, outcomes, syllabus, and learning resources.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document outlines the academic rules and regulations for a course on Formal Languages and Automata Theory. It includes information on course code, category, credits, prerequisites, outcomes, syllabus, and learning resources.

    Copyright:

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

    20BS1403

    Uploaded by

    20501a05b9
    This document outlines the academic rules and regulations for a course on Formal Languages and Automata Theory. It includes information on course code, category, credits, prerequisites, outcomes, syllabus, and learning resources.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Academic Rules and Regulations PVP20

    Formal Languages and Automata Theory

    Course Code 20BS1403 Year II Semester II


    Course
    BS Branch CSE Course Type Theory
    Category
    Discrete Mathematical
    Credits 3 L-T-P 3-0-0 Prerequisites Structures
    Continuous
    Semester End
    Internal 30 70 Total Marks: 100
    Evaluation:
    Evaluation :

    Course Outcomes
    Upon successful completion of the course, the student will be able to
    Understand the fundamental concepts of Formal Languages and L2
    CO1
    Automata.
    Apply the knowledge of Automata Theory, Grammars & Regular L3
    CO2
    Expressions for solving various problems.
    CO3 Apply different Turing machines techniques to solve problems. L3

    CO4 Analyze automata and their computational power to recognize languages. L4

    Contribution of Course Outcomes towards achievement of Program Outcomes & Strength of correlations
    (3:Substantial, 2: Moderate, 1:Slight)

    PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2

    CO1 3

    CO2 3 1

    CO3 2

    CO4 3 1 1 1

    Syllabus
    Unit
    Contents Mapped CO
    No.
    Automata: Why study Automata Theory?, The central Concepts of Automata
    Theory. CO1, CO2,
    I Finite Automata: Deterministic Finite Automata, Non-Deterministic Finite CO4
    Automata, Finite Automata with Epsilon Transitions, Finite Automata with
    Outputs(without conversions)

    100
    Academic Rules and Regulations PVP20

    Regular Expressions and Languages: Regular Expressions, Finite Automata


    and Regular Expressions, Algebraic Laws for Regular expressions (without
    proofs). CO1, CO2
    II Properties of regular Languages: Proving Languages not to be regular, Closure
    properties of Regular Languages (without proofs), Equivalence and Minimization
    of Automata.
    Context–free grammars and Languages: Context–free grammars, Parse trees,
    Ambiguity in grammars and Languages, CO1, CO2
    III Properties of Context-free languages: Normal Forms for Context Free
    Grammars, The Pumping Lemma For Context Free Languages
    Pushdown Automata: Definition of the Pushdown Automaton, The Languages CO1, CO2,
    IV of a PDA, Equivalence of PDA‗s and CFG‗s, Deterministic Pushdown CO4
    Automaton.
    Turing Machines: Problems that computer cannot solve, The Turing Machine,
    Programming Techniques for Turing Machine, Extensions to the Basic Turing CO1,CO2,
    V Machine CO3, CO4
    Undecidability: Recursively Enumerable Language, Universal Turing Machines
    (UTM), Halting Problem, Post Correspondence Problem, Church Hypothesis.
    Learning Resources
    Text Books
    1. Introduction to Automata Theory, Languages and Computations, J.E.Hopcroft, R.Motwani and J.D
    Ullman, Third Edition, Pearson Education.
    2. Theory of Computer Science, Automata languages and computation, Mishra, Chandra Shekaran,
    Second Edition, PHI.
    Reference Books
    1. Introduction of the Theory and Computation, Michael Sipser, 1997, Thomson Brokecole.
    2. Elements of The theory of Computation, H.R.Lewis and C.H.Papadimitriou, Second Edition, 2003,
    Pearson Education/PHI.
    3. Formal Languages and Automata Theory, Basavarj S. Anami, Karibasappa K.G, WILEYINDIA.
    4. Introduction to Languages and the Theory of Computation, J.C.Martin, Third Edition, TMH, 2003.
    e- Resources & other digital material

    1. https://www.udemy.com/course/formal-languages-and-automata-theory-e/
    2. https://eecs.wsu.edu/~ananth/CptS317/
    3. https://nptel.ac.in/courses/106/103/106103070/
    4. https://nptel.ac.in/courses/106/106/106106049/
    5. https://nptel.ac.in/courses/111/103/111103016/
    6. https://nptel.ac.in/courses/106/105/106105196/

    101

    You might also like