Scribd Logo
Upload

Welcome to Scribd!

  • 51 views

    Gujarat Technological University: Theory of Computation 6 Semester

    Uploaded by

    Er Umesh Thoriya
    This document outlines the Theory of Computation course for the 6th semester Bachelor of Engineering program. It covers topics including regular languages and finite automata, context-free grammar, pushdown automata, Turing machines, and concepts of undecidability and computable functions. The course aims to teach how to identify computational limitations through formal models and apply mathematical techniques to analyze problems. Students will learn to classify languages, construct grammars and automata, and analyze concepts like undecidability. Assessment includes a theory exam worth 70 marks and a practical exam worth 30 marks.

    Copyright:

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

    Gujarat Technological University: Theory of Computation 6 Semester

    Uploaded by

    Er Umesh Thoriya
    51 views3 pages
    This document outlines the Theory of Computation course for the 6th semester Bachelor of Engineering program. It covers topics including regular languages and finite automata, context-free grammar, pushdown automata, Turing machines, and concepts of undecidability and computable functions. The course aims to teach how to identify computational limitations through formal models and apply mathematical techniques to analyze problems. Students will learn to classify languages, construct grammars and automata, and analyze concepts like undecidability. Assessment includes a theory exam worth 70 marks and a practical exam worth 30 marks.

    Original Title

    3160704

    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 Theory of Computation course for the 6th semester Bachelor of Engineering program. It covers topics including regular languages and finite automata, context-free grammar, pushdown automata, Turing machines, and concepts of undecidability and computable functions. The course aims to teach how to identify computational limitations through formal models and apply mathematical techniques to analyze problems. Students will learn to classify languages, construct grammars and automata, and analyze concepts like undecidability. Assessment includes a theory exam worth 70 marks and a practical exam worth 30 marks.

    Copyright:

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

    Gujarat Technological University: Theory of Computation 6 Semester

    Uploaded by

    Er Umesh Thoriya
    This document outlines the Theory of Computation course for the 6th semester Bachelor of Engineering program. It covers topics including regular languages and finite automata, context-free grammar, pushdown automata, Turing machines, and concepts of undecidability and computable functions. The course aims to teach how to identify computational limitations through formal models and apply mathematical techniques to analyze problems. Students will learn to classify languages, construct grammars and automata, and analyze concepts like undecidability. Assessment includes a theory exam worth 70 marks and a practical exam worth 30 marks.

    Copyright:

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

    GUJARAT TECHNOLOGICAL UNIVERSITY

    Bachelor of Engineering
    Subject Code: 3160704
    THEORY OF COMPUTATION
    6thSEMESTER

    Type of course: NA

    Prerequisite: Calculus, Data Structures and Algorithms, Set Theory

    Rationale: Theory of computation teaches how efficiently problems can be solved on a model of
    computation. The main thrust is to identify the limitations of the computers through formalizing
    computation (by introducing several models including Turing Machines) and applying mathematical
    techniques to the formal models obtained. It is also necessary to learn the ways in which computer can be
    made to think. Finite state machines can help in natural language processing which is an emerging area.

    Teaching and Examination Scheme:


    Teaching Scheme Credits Examination Marks Total
    L T P C Theory Marks Practical Marks Marks
    ESE (E) PA (M) ESE (V) PA (I)
    4 1 0 5 70 30 0 0 100

    Content:

    Sr Course content Total Hrs %Wei


    No ghtage

    1 Review of Mathematical Theory: 04 10


    Sets, Functions, Logical statements, Proofs, Relations, Languages, Principal of
    Mathematical Induction, Strong Principle, Recursive Definitions, Structural
    Induction.
    2 Regular Languages and Finite Automata: 12 25
    Regular Expressions, Regular Languages, Application of Finite Automata,
    Automata with output - Moore machine & Mealy machine, Finite Automata,
    Memory requirement in a recognizer, Definitions, union- intersection and
    complement of regular languages, Non Deterministic Finite Automata, Conversion
    from NFA to FA, - Non Deterministic Finite Automata, Conversion of NFA- 
    to NFA, Kleene’s Theorem, Minimization of Finite automata, Regular And Non
    Regular Languages – pumping lemma.

    3 Context free grammar (CFG): 08 15


    Definitions and Examples, Unions Concatenations And Kleene’s of Context free
    language, Regular Grammar for Regular Language, Derivations and Ambiguity ,
    Unambiguous CFG and Algebraic Expressions, BacosNaur Form (BNF), Normal
    Form – CNF.
    4 Pushdown Automata, CFL And NCFL: 08 15
    Definitions, Deterministic PDA, Equivalence of CFG and PDA & Conversion,
    Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL.

    5 Turing Machine (TM): 08 15

    Page 1 of 3
    w.e.f. AY 2018-19
    GUJARAT TECHNOLOGICAL UNIVERSITY
    Bachelor of Engineering
    Subject Code: 3160704
    TM Definition, Model Of Computation, Turing Machine as Language Acceptor,
    TM that Compute Partial Function, Church Turning Thesis, Combining TM,
    Variations Of TM, Non Deterministic TM, Universal TM, Recursively and
    Enumerable Languages, Context sensitive languages and Chomsky hierarchy.
    6 Computable Functions: 04 10
    Partial - Total - Constant Functions, Primitive Recursive Functions, Bounded
    Mineralization, Regular function, Recursive Functions, Quantification,
    Minimalization, and μ-Recursive Functions, All Computable Functions Are μ-
    Recursive
    7 Undecidability : 04 10
    A Language That Can’t Be Accepted, and a Problem That Can’t Be Decided , Non
    Recursive Enumerable (RE) Language – Undecidable Problem with RE –
    Undecidable Problems about TM – Undecidable Problems Involving Context-Free
    Languages, Post‘s Correspondence Problem, The Class P and NP.

    Suggested Specification table with Marks (Theory):

    Distribution of Theory Marks

    R Level U Level A Level N Level E Level C Level


    15 25 25 5 00 00
    Legends: R: Remembrance; U: Understanding; A: Application, N: Analyze and E: Evaluate C:
    Create and above Levels (Revised Bloom’s Taxonomy)

    Note: This specification table shall be treated as a general guideline for students and teachers. The actual
    distribution of marks in the question paper may vary slightly from above table.

    Reference Books:

    1. Introduction to Languages and the Theory of Computation, 4th by John Martin, Tata Mc Graw Hill
    2. An introduction to automata theory and formal languages By Adesh K. Pandey, Publisher: S.K.
    Kataria& Sons
    3. Introduction to computer theory By Deniel I. Cohen , Joh Wiley & Sons, Inc
    4. Computation: Finite and Infinite By Marvin L. Minsky Prentice-Hall
    5. Compiler Design By Alfred V Aho, Addison Weslley
    6. Introduction to the Theory of Computation By Michael Sipser
    7. Automata Theory, Languages, and Computation By John Hopcroft, Rajeev Motowani, and Jeffrey
    Ullman

    Course Outcome:

    Sr. Marks %
    CO statement
    No. weightage
    CO-1 Use the concepts and techniques of discrete mathematics for theoretical 10%
    computer science.

    Page 2 of 3
    w.e.f. AY 2018-19
    GUJARAT TECHNOLOGICAL UNIVERSITY
    Bachelor of Engineering
    Subject Code: 3160704
    CO-2 Identify different formal languages and their relationship. 25%
    CO-3 Classify and construct grammars for different languages and vice-versa. 25%
    CO-4 Build finite automata, push down automata and turing machine. 25%
    CO-5 Analyze various concepts of undecidability and Computable Function 15%
    and Discuss analytically and intuitively for problem-solving situation.

    List of Open Source Software/learning website:


    1. http://en.wikipedia.org/wiki/Theory_of_computation
    2. http://meru.cecs.missouri.edu/courses/cecs341/tc.html
    3. https://www.geeksforgeeks.org/introduction-of-theory-of-computation/
    4. http://www.vssut.ac.in/lecture_notes/lecture1428551440.pdf
    5. https://nptel.ac.in/courses/106/104/106104028/

    Page 3 of 3
    w.e.f. AY 2018-19

    You might also like