Scribd Logo
Upload

Welcome to Scribd!

  • 195 views

    Anand Institute of Higher Technology KAZHIPATTUR - 603 103

    Uploaded by

    addssdfa
    This document outlines the lecture plan for the course "Theory of Computation". The course will cover automata fundamentals, regular expressions and languages, context-free grammars and languages, properties of context-free languages, Turing machines, and issues of decidability. Over 50 lectures will teach these topics through various teaching methods including lectures, group discussions, quizzes, and experimental learning activities. Assignments and tutorials are also included to reinforce the concepts covered.

    Copyright:

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

    Anand Institute of Higher Technology KAZHIPATTUR - 603 103

    Uploaded by

    addssdfa
    195 views4 pages
    This document outlines the lecture plan for the course "Theory of Computation". The course will cover automata fundamentals, regular expressions and languages, context-free grammars and languages, properties of context-free languages, Turing machines, and issues of decidability. Over 50 lectures will teach these topics through various teaching methods including lectures, group discussions, quizzes, and experimental learning activities. Assignments and tutorials are also included to reinforce the concepts covered.

    Original Title

    CS8501 BE-TOC-R2017

    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 lecture plan for the course "Theory of Computation". The course will cover automata fundamentals, regular expressions and languages, context-free grammars and languages, properties of context-free languages, Turing machines, and issues of decidability. Over 50 lectures will teach these topics through various teaching methods including lectures, group discussions, quizzes, and experimental learning activities. Assignments and tutorials are also included to reinforce the concepts covered.

    Copyright:

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

    Anand Institute of Higher Technology KAZHIPATTUR - 603 103

    Uploaded by

    addssdfa
    This document outlines the lecture plan for the course "Theory of Computation". The course will cover automata fundamentals, regular expressions and languages, context-free grammars and languages, properties of context-free languages, Turing machines, and issues of decidability. Over 50 lectures will teach these topics through various teaching methods including lectures, group discussions, quizzes, and experimental learning activities. Assignments and tutorials are also included to reinforce the concepts covered.

    Copyright:

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

    ANAND INSTITUTE OF HIGHER TECHNOLOGY

    KAZHIPATTUR – 603 103

    Department of Computer Science and Engineering

    Academic Year: 2019-20 (Odd Semester)

    (Regulation 2017)

    Lecture Plan

    Course Code & Title: CS8501 Theory of Computation

    Semester & Branch: V Semester B.E. Computer Science and Engineering

    Name of the Faculty member: Mr.S.Praveen Kumar

    Designation & Department: AP / CSE

    Course Objectives:

    At the end of the course, the students will be able to:

    1. To understand the language hierarchy

    2. To construct automata for any given pattern and find its equivalent regular
    expressions

    3. To design a context free grammar for any given language

    4. To understand Turing machines and their capability

    5. To understand undecidable problems and NP class problems

    Course Outcomes:

    After completion of the course, the student should be able to:

    1. Construct automata, regular expression for any pattern.

    2. Write Context free grammar for any construct.

    3. Design Turing machines for any language.

    4. Propose computation solutions using Turing machines.

    5. Derive whether a problem is decidable or not.


    Lecture Topic(s) to be covered Teaching aids Teaching Methodology
    No. (Board / LCD) (Lecture
    Role play
    Group Discussion
    Quiz
    Debates
    Gamefication)
    1 Unit I AUTOMATA Board Lecture
    FUNDAMENTALS
    Introduction to formal proof
    2 Additional forms of Proof Board Lecture

    3 Inductive Proofs Board Lecture

    4 Finite Automata Board Lecture

    5 Deterministic Finite Board Lecture


    Automata
    6,7 Non-deterministic Finite Board Lecture
    Automata
    8 Finite Automata with Epsilon Board Lecture
    Transitions
    9 Unit Test-I Board Lecture

    10 UNIT II REGULAR Board Lecture


    EXPRESSIONS AND
    LANGUAGES
    Regular Expressions
    11,12 FA and Regular Expressions Board Group discussion

    13,14 Proving Languages not to be Board Lecture


    regular
    15,16 Closure Properties of Regular LCD Group discussion
    Languages
    17 Equivalence and Board Lecture
    Minimization of Automata
    18 Unit test – II Board Lecture

    19 UNIT III CONTEXT Board Lecture


    FREE GRAMMAR AND
    LANGUAGES
    CFG & Parse Trees
    20,21 Ambiguity in Grammars and Board Lecture
    Languages
    22,23 Definition of the Pushdown Board Lecture
    Automata
    24,25 Languages of a Pushdown Board Lecture
    Automata
    26 Equivalence of Pushdown Board Lecture
    Automata and CFG
    27 Deterministic Pushdown Board Debate
    Automata
    28 Unit test-III Board Lecture

    29,30,31 UNIT IV PROPERTIES Board Lecture


    OF CONTEXT FREE
    LANGUAGES
    Normal Forms for CFG
    32,33 Pumping Lemma for CFL Board Lecture

    34,35 Closure Properties of CFL LCD Group discussion

    36,37 Turing Machines Board Lecture

    38 Programming Techniques for Board Lecture


    TM
    39 Unit test-IV Board Lecture

    40 UNIT V Board Lecture


    UNDECIDABILITY
    Non Recursive Enumerable
    (RE) Language
    41,42 Undecidable Problem with Board Lecture
    RE
    43 Undecidable Problems about Board Lecture
    TM
    44 Post‘s Correspondence Board Quiz
    Problem
    45 The Class P and NP. LCD Lecture

    46 NP hard and complete Board Group discussion

    47 Phases of Compiler Board Lecture


    48 Regular Expression to LCD Experimental Learning
    minimized DFA Conversion
    Content Beyond the Syllabus
    49 Phases of Compiler Board Lecture
    Mini Project
    50 Visualization of finite LCD Experimental Learning
    automata

    Assignment-1:
    1. Conversion of NFA with Epsilon to NFA without Epsilon

    2. Construction of Finite Automata

    Assignment-2:

    1. Design of Pushdown Automata

    2. Construction of Turing Machine

    Tutorials:

    1.Describe what happens when you attempt to use the pumping lemma to show that

    some finite (and hence regular) language is not regular.

    2.Let Σ = {0, 1, +, =} and A = { x + y = z | x, y, z are binary integers and z is the sum

    of x and y }. Prove that A is not regular.

    Textbooks:

    1. J.E.Hopcroft, R.Motwani and J.D Ullman, ―Introduction to Automata Theory,


    Languages and Computations‖, Second Edition, Pearson Education, 2003.
    References:
    1. Unit I: H.R.Lewis and C.H.Papadimitriou, ―Elements of the theory of Computation‖,
    Second Edition,HI, 2003.
    2. Unit II: : H.R.Lewis and C.H.Papadimitriou, ―Elements of the theory of Computation‖,
    Second Edition,HI, 2003.
    3. Unit III: :J.Martin Introduction to Languages and the Theory of Computation‖, Third
    Edition, TMH, 2003.
    4. Unit IV: J.Martin Introduction to Languages and the Theory of Computation‖, Third
    Edition, TMH, 2003.
    5. Unit V: J.Martin, ―Introduction to Languages and the Theory of Computation‖, Third
    Edition, TMH, 2003. & Micheal Sipser, ―Introduction of the Theory and Computation‖,
    Thomson Brokecole, 1997.

    Prepared by: Approved by:

    Mr.S.Praveen Kumar, AP/CSE Dr.S.RoselinMary, HOD/CSE

    (Name & Signature of Faculty member) (Name & Signature of HOD)

    You might also like