Scribd Logo
Upload

Welcome to Scribd!

  • 73 views

    Theory of Computation

    Uploaded by

    Anuj
    This document provides an overview of the ICS 221 Theory of Computation course. The course is 4 credits and meets 3 times per week. Grading is based on midterms, quizzes, assignments, and a final exam. The course introduces formal languages, finite state machines, regular expressions, context-free grammars, pushdown automata, Turing machines, and complexity classes. Topics include regular and context-free languages, decidability, and computational complexity. Recommended textbooks are listed.

    Copyright:

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

    Theory of Computation

    Uploaded by

    Anuj
    73 views10 pages
    This document provides an overview of the ICS 221 Theory of Computation course. The course is 4 credits and meets 3 times per week. Grading is based on midterms, quizzes, assignments, and a final exam. The course introduces formal languages, finite state machines, regular expressions, context-free grammars, pushdown automata, Turing machines, and complexity classes. Topics include regular and context-free languages, decidability, and computational complexity. Recommended textbooks are listed.

    Original Description:

    Theory of Computation

    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 an overview of the ICS 221 Theory of Computation course. The course is 4 credits and meets 3 times per week. Grading is based on midterms, quizzes, assignments, and a final exam. The course introduces formal languages, finite state machines, regular expressions, context-free grammars, pushdown automata, Turing machines, and complexity classes. Topics include regular and context-free languages, decidability, and computational complexity. Recommended textbooks are listed.

    Copyright:

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

    Theory of Computation

    Uploaded by

    Anuj
    This document provides an overview of the ICS 221 Theory of Computation course. The course is 4 credits and meets 3 times per week. Grading is based on midterms, quizzes, assignments, and a final exam. The course introduces formal languages, finite state machines, regular expressions, context-free grammars, pushdown automata, Turing machines, and complexity classes. Topics include regular and context-free languages, decidability, and computational complexity. Recommended textbooks are listed.

    Copyright:

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

    ICS 221 Theory of

    Computation
    Dr Ebin Deni Raj
    Prerequisites
    O IMA 111 Mathematics I
    Course Outline
    O 4 credits
    O 4 hours a week
    Class schedule
    O Tuesday – 9:00-10:25
    O Wednesday-9:00-10:25
    O Thursday- 8:00-8:55
    Rules and Regulations
    O Mobile phones/ other electronic gadgets
    should be switched off.
    O Assignments should be submitted before the
    deadline.
    O There will not be re-quiz.
    O Attendance is compulsory.
    Course Grading Policy
    Evaluation type Grade points/Marks

    Mid Term 1 20

    Mid Term 2 20

    Quiz/Assignment 10

    End Semester Examination 50

    Total Marks 100


    Objectives of the Course
    O Course will provide a formal connection
    between algorithmic problem solving and the
    theory of languages and automata and develop
    them into a mathematical (and less magical)
    view towards algorithmic design and in
    general computation itself.
    Outcome of the Course
    O Model, compare and analyse different
    computational models using combinatorial
    methods
    O Apply rigorously formal mathematical
    methods to prove properties of languages,
    grammars and automata
    O An overview of how the theoretical study in
    this course is applicable to and engineering
    application like designing the compilers.
    Topics/lessons
    Syllabus
    Introduction : Notion of formal language- Strings, Alphabet, Language, Operations, Finite
    State Machine, definitions, finite automation model, acceptance of strings and languages,
    deterministic finite automation, equivalence between NFA and DFA, Conversion of NFA
    into DFA, minimization of FSM ,equivalence between two FSM's, Moore and Mealy
    machines.

    Regular expressions: Regular sets, regular expressions, identity rules, manipulation of


    regular expressions, equivalence between RE and FA, inter conversion, Pumping lemma,
    Closure properties of regular sets regular grammars, right linear and left linear grammars
    equivalence between regular linear grammar and FA, inter conversion between RE and RG.

    Context free grammars: Derivation, parse trees. Language generated by a CFG.


    Eliminating useless symbols, -productions, unit productions. Chomsky normal form.
    Pushdown automata: Definition, instantaneous description as a snapshot of PDA
    computation, notion of acceptance for PDAs.

    Turing machine: Turing machine, definition, model, design of TM, Computable Functions,
    recursive enumerable language, Church’s Hypothesis, Counter machine, types of TM's, RAM
    machine

    Un-decidability and classes of problems: Chomsky hierarchy of languages, linear


    bounded automata and context sensitive language, Grammar, decidability of problems,
    Universal Turing Machine, un-decidability of post’s correspondence problem. Turing
    reducibility logical theories Complexity classes: P, NP, co-NP, EXP, PSPACE, L, NL,
    ATIME, BPP, RP, ZPP, IP.
    Textbooks/References
    Text
    1. M Sipser, Introduction to the Theory of Computation, 2nd Ed., Thomson, 2005
    2. Lewis H.P. & Papadimition C.H. Elements of Theory of Computation, Prentice Hall of
    India, 4th edition. 2007
    Reference Books
    1. S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge
    University Press,2009.
    2. C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing
    Company, 1994.
    3. D. C. Kozen, Theory of Computation, Springer, 2006.
    4. D. S. Garey, G. Johnson, Computers and Intractability: A Guide to the Theory of NP-
    Completeness, Freeman, New York, 1979.
    5. J Hopcroft, JD Ullman, R Motwani, Introduction to Automata Theory, Languages and
    Computation, 3rd Ed., Pearson, 2008.

    You might also like