Scribd Logo
Upload

Welcome to Scribd!

  • 69 views

    TCS Unit 1 Introduction

    Uploaded by

    Vedashree Shetye
    The document provides an introduction to theoretical computer science and automata theory. It discusses how automata theory studies mathematical machines called automata and computational problems that can and cannot be solved using these machines. Automata theory establishes what problems are solvable by computers. The document outlines several key topics that will be covered, including finite state machines, pushdown automata, Turing machines, and their applications in compiler construction. It also lists recommended textbooks and reference books on the subject.

    Copyright:

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

    TCS Unit 1 Introduction

    Uploaded by

    Vedashree Shetye
    69 views23 pages
    The document provides an introduction to theoretical computer science and automata theory. It discusses how automata theory studies mathematical machines called automata and computational problems that can and cannot be solved using these machines. Automata theory establishes what problems are solvable by computers. The document outlines several key topics that will be covered, including finite state machines, pushdown automata, Turing machines, and their applications in compiler construction. It also lists recommended textbooks and reference books on the subject.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides an introduction to theoretical computer science and automata theory. It discusses how automata theory studies mathematical machines called automata and computational problems that can and cannot be solved using these machines. Automata theory establishes what problems are solvable by computers. The document outlines several key topics that will be covered, including finite state machines, pushdown automata, Turing machines, and their applications in compiler construction. It also lists recommended textbooks and reference books on the subject.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    69 views23 pages

    TCS Unit 1 Introduction

    Uploaded by

    Vedashree Shetye
    The document provides an introduction to theoretical computer science and automata theory. It discusses how automata theory studies mathematical machines called automata and computational problems that can and cannot be solved using these machines. Automata theory establishes what problems are solvable by computers. The document outlines several key topics that will be covered, including finite state machines, pushdown automata, Turing machines, and their applications in compiler construction. It also lists recommended textbooks and reference books on the subject.

    Copyright:

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

    Theoretical Computer Science

    Prof. Manisha Tiwari


    (Computer Engineering Department)
    MPSTME, NMIMS University
    Introduction to Theory of Computation (TOC)

    • ‘TOC’ : Study of ‘mathematical’ machines or systems called automata

    • Study of computational problems that can and cannot be solved using these machines, i.e.
    what is the extent to which a problem is solvable on a computer.
    What is automata theory?
    Automata: A self operating machine

    “Automatically follow a predetermined sequence of operations, or respond to predetermined


    instructions”

    An automation theory (a mathematical model) is an abstract machine (considered as hardware


    or software) i.e. computer system constructed to allow a detailed analysis of how the computer
    system works.
    Who discovered automata theory?

    Turing Test: computer is capable of thinking like


    a human being

    When the task is computable?


    Let’s watch a small video !!

    Link:

    https://www.youtube.com/watch?v=SV57Yv8BXBc
    ICA (50 M internal and 50 M external)
    Text Books/Reference Books

    1. Introduction to Formal Languages and Automata, 4e, Peter Linz, Narosa


    2. Introduction to Automata Theory, Languages and Computation, 3e, J.E. Hopcroft, J.D. Ullman, Motwani, Pearson
    Edu., 2008.
    3. Introduction to Languages and the Theory of Computation, J.C. Martin, TMH, SIE, 2007
    Unit Description Duration
    1 Introduction to Automata theory: Basic concepts of symbol, alphabet, String, Language, Grammar and 3
    Automata, Application of the subject in complies construction.
    2 Finite State Machine & Regular Set: Concept of DFA, NFA, Epsilon NFA, Converting NFA to Minimized 8
    DFA, Regular Expressions, DFA to R. E Conversion, Regular language, Closure properties & Pumping
    Lemma for regular sets
    3 Moore and Mealy machine: examples of Moore & Mealy machines, converting Moore machines to Mealy 3
    machines, converting Mealy machines to Moore machines.
    4 Context Free Grammar: Basic concept of Context Free Grammar and Language, Ambiguous CFG, 5
    Simplification of CFG, Chomsky's Normal Form, Griebach Normal Form
    5 Push Down Automata: Elements in PDM, Power of PDA over FSM. Design of PDA for CFL, Closure 5
    Properties of CFL, Pumping Lemma for CFLs.
    6 Turing Machine: Turing Machine Definition, Turing machine as acceptor and generator, Examples of TM 6
    designing, Types of Turing machine, Universal Turing machine, Church Turing Hypothesis, Halting
    problem,Power of TM over PDA
    Unit 1 : Introduction to Automata theory

    • Basic concepts of String

    • Formal languages

    • Chomsky hierarchy

    • Grammar and its type – Type 0, 1, 2 and 3

    • Derivation Tree

    • Application of the subject in complier construction


    SET THEORY
    SET OPERATION
    Language
    Formal Language
    Language “This is my book”

    Syntax(rules)
    Proper use of grammar
    Grammar

    formed by strings

    Words Strings : this, is, my, book

    Composed by
    letters : ‘t’, ‘h’ ,‘I’, ‘s’, ‘I’ ,‘s’,
    letters ‘m’,’y’, ‘b’,’o’,’o’,’k’

    Proper use of rules to form a string that is acceptable by machine is called formal languages
    Formal Language and Automata Theory

    (Infinite strings)

    “ Design a machine which takes input a, b and produce output strings starts with b and ends with a”

    Letters: {a, b, 0, 1}
    Input (alphabets) : a,b
    Strings: a,b,ab, aab, baa, bbaa, bbbbba, baaaab. baba………
    Language (L) : baa, baba, bbaa, bbbbba…
    DEFINITION

    Symbol: A symbol is a user-defined entity.

    Alphabet: An alphabet is a finite set of symbols denoted by Σ in automata. Alphabets are a set of symbols used
    to construct a language. Example, {0, 1} is binary alphabet, {A…, Z, a…z} is the alphabet set for the English
    language.

    String: A string is defined as a sequence of symbols of finite length. A string is denoted by w in automata.
    Example, 000111 is a binary string.

    (Length of a string w is denoted by |w|. For the previous case, |w| = |000111| = 6).
    Chomsky Hierarchy
    Applications : Vending Machines using ToC
    Application :GAME
    Applications of TOC in Compiler Construction
    Grammar in TOC

    Grammar in theory of computation is a finite set of formal rules that are generating syntactically correct
    sentences.
    THANK
    YOU

    You might also like