Scribd Logo
Upload

Welcome to Scribd!

  • 39 views

    Lesson Teaching Plan: Subject: Automata Theory Branch: Computer Application Semester: 4 Faculty Name: Bighnaraj Naik

    Uploaded by

    santhi saranya
    This document provides a lesson teaching plan for an Automata Theory course taught over one semester. The plan outlines 8 modules that will be covered over 42 class periods. Module topics include finite automata, regular expressions, context-free grammars, pushdown automata, properties of context-free languages, Turing machines, and undecidability. Each module breaks down the topics and number of classes required to cover the material.

    Copyright:

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

    Lesson Teaching Plan: Subject: Automata Theory Branch: Computer Application Semester: 4 Faculty Name: Bighnaraj Naik

    Uploaded by

    santhi saranya
    39 views2 pages
    This document provides a lesson teaching plan for an Automata Theory course taught over one semester. The plan outlines 8 modules that will be covered over 42 class periods. Module topics include finite automata, regular expressions, context-free grammars, pushdown automata, properties of context-free languages, Turing machines, and undecidability. Each module breaks down the topics and number of classes required to cover the material.

    Original Description:

    Lesson 1493761950

    Original Title

    Lesson 1493761950

    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 provides a lesson teaching plan for an Automata Theory course taught over one semester. The plan outlines 8 modules that will be covered over 42 class periods. Module topics include finite automata, regular expressions, context-free grammars, pushdown automata, properties of context-free languages, Turing machines, and undecidability. Each module breaks down the topics and number of classes required to cover the material.

    Copyright:

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

    Lesson Teaching Plan: Subject: Automata Theory Branch: Computer Application Semester: 4 Faculty Name: Bighnaraj Naik

    Uploaded by

    santhi saranya
    This document provides a lesson teaching plan for an Automata Theory course taught over one semester. The plan outlines 8 modules that will be covered over 42 class periods. Module topics include finite automata, regular expressions, context-free grammars, pushdown automata, properties of context-free languages, Turing machines, and undecidability. Each module breaks down the topics and number of classes required to cover the material.

    Copyright:

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

    Lesson Teaching Plan

    Subject: Automata Theory Branch: Computer Application


    Semester: 4th Sem Faculty name: Bighnaraj Naik

    Module Topic No. of classes


    1 Introduction to Automata: The Methods Introduction to Finite 1
    Automata, Structural Representations, Automata and Complexity.
    Proving Equivalences about Sets
    Proof by Contradiction, Inductive Proofs: General Concepts of 1
    Automata Theory: Alphabets Strings, Languages, Applications of
    Automata Theory.
    2 Finite Automata: The Ground Rules, The Protocol, Deterministic 1
    Finite Automata: Definition of a Deterministic Finite Automata
    How a DFA Processes Strings, Simpler Notations for DFA’s, 1
    Extending the Transition Function to Strings
    The Language of a DFA, Nondeterministic Finite Automata: An 1
    Informal View.
    The Extended Transition Function, The Languages of an NFA, 1
    Equivalence of Deterministic and Nondeterministic Finite
    Automata.
    Finite Automata With Epsilon-Transitions: Uses of -Transitions 1
    The Formal Notation for an -NFA, Epsilon-Closures, Extended 1
    Transitions and Languages for -NFA’s
    Eliminating -Transitions. 1
    3 Regular Expressions and Languages: Regular Expressions: The 1
    Operators of regular Expressions, Building Regular Expressions
    Precedence of Regular-Expression Operators, Precedence of 1
    Regular-Expression Operators, Finite Automata and Regular
    Expressions: From DFA’s to Regular Expressions
    Converting DFA’s to Regular Expressions 1
    Converting DFA’s to Regular Expressions by Eliminating States 1
    Converting Regular Expressions to Automata. Algebraic Laws for 1
    Regular Expressions
    Properties of Regular Languages: The Pumping Lemma for Regular 1
    Languages
    Applications of the Pumping Lemma Closure Properties of Regular 1
    Languages
    Decision Properties of Regular Languages, Equivalence and 1
    Minimization of Automata
    4 Context-Free Grammars and Languages: Definition of Context-Free 1
    Grammars, Derivations Using a Grammars Leftmost and Rightmost
    Derivations, The Languages of a Grammar,
    Parse Trees: Constructing Parse Trees, The Yield of a Parse Tree, 1
    Inference Derivations, and Parse Trees, From Inferences to Trees,
    From Trees to Derivations, From Derivation to Recursive 1
    Inferences,
    Applications of Context-Free Grammars: Parsers
    Ambiguity in Grammars and Languages: Ambiguous Grammars, 1
    Removing Ambiguity From Grammars, Leftmost Derivations as a
    Way to Express Ambiguity, Inherent Ambiguity
    5 Pushdown Automata: Definition Formal Definition of Pushdown 1
    Automata, A Graphical Notation for PDA’s, Instantaneous
    Descriptions of a PDA,
    The Languages of a PDA: Acceptance by Final State, Acceptance by 1
    Empty Stack
    From Empty Stack to Final State, From Final State to Empty Stack 1
    Equivalence of PDA’s and CFG’s: 1
    From Grammars to Pushdown Automata, 1
    From PDA’s to Grammars 1
    Deterministic Pushdown Automata: Definition of a Deterministic 1
    PDA, Regular Languages and Deterministic PDA’s, DPDA’s and
    Context-Free Languages, DPDA’s and Ambiguous Grammars
    6 Properties of Context-Free Languages: Normal Forms for Context- 1
    Free Grammars, The Pumping Lemma for Context-Free Languages,
    Closure Properties of Context-Free Languages, Decision Properties 2
    of CFL’s
    7 Introduction to Turing Machines: The Turing Machine: The 2
    Instantaneous Descriptions for Turing Machines
    Transition Diagrams for Turing Machines, The Language of a 2
    Turing Machine
    Turing Machines and Halting, Programming Techniques for Turing 1
    Machines, Extensions to the Basic Turing Machine
    Restricted Turing Machines, Turing Machines and Computers 1
    8 Undecidability: A Language That is Not Recursively Enumerable, 1
    Enumerating the Binary Strings, Codes for Turing Machines
    An Un-decidable Problem That Is RE: Recursive Languages, 1
    Complements of Recursive and RE languages
    The Universal Languages, Un-decidability of the Universal 1
    Language
    Un-decidable Problems About Turing Machines: Reductions, Turing
    Machines That Accept the Empty Language
    Post’s Correspondence Problem: Definition of Post’s 1
    Correspondence Problem, The “Modified” PCP, Other Un-decidable
    Problems: Un-decidability of Ambiguity for CFG’s

    Total no. of classes: 42

    You might also like